admin
[欢迎关注、分享、称赞或评论。你举手的辛苦是最大的鼓励！【成语】
感谢您对[PHP在路上]每天一点一点进步的关注。
码字不容易，尊重版权，转载请注明出处：PHP在路上。
前言：提到算法，必然会讨论算法复杂度。不少非计算机专业的程序员在参与算法讨论时，多少会有点尴尬（算法复杂度到底是个什么东西）。
内容概要：
1、算法复杂度
2、时间复杂度
3、空间复杂度
4、总结
一、算法复杂度
其实算法复杂度是一个概念，一定程度上反映一个算法的好坏程度。算法复杂度分为两个部分，时间复杂度和空间复杂度。时间复杂度反应算法执行的时间长短，空间复杂度反应是算法占用内存(或叫存储空间)的大小。
必须说一下，所谓的复杂度，不是一个具体的值，只是一个估值，在比较两种算法优劣时使用。
二、时间复杂度
时间复杂度就是是一个函数，这个函数含有两个变量，一个算法的运行时间，一个算法要处理数据的数量。
这里有一个关系：处理数据的数量越大，算法运行的次数和时间越长。
假设处理数据的数量是n，算法运行的次数就是f(n)。这里的f()是一个函数，它的大小随着n增大而增大，数学上叫单调递增函数。
如果我们把算法的时间复杂度记为T(n);那他的值和算法运行的次数f(n)是有关的，随着n的增大，算法执行时间的增长率和运行次数的增长率是正比例关系。所以f(n)越小，算法的质量越高，算法时间复杂度越低。
所以，在计算时间复杂度T(n)的时候，步骤如下：
1、先要拿出算法的基本单元。
2、根据相应的各语句确定它的执行次数f(n)。
3、找出T（n）的同数量级，将这个同数量等级赋值给f(n)。
4、因为T(n)/f(n)求极限可以得到一个常数C。（求极限值是高等数学内容，自行百度脑补一下），我们可以确定时间的复杂度T(n) = O(f(n));
其中，同数量等级有：1，Log2n ，n ，nLog2n ，n^2，n^3，2^n，n!,n^n。
总结：常用的时间复杂度所耗费的时间从小到大依次是：O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
三、空间复杂度
空间复杂度是指算法在内存内所需要的存储空间的度量，一般是指除正常占用内存开销外的辅助存储单元规模。和时间复杂度类似，这样标记：S(n)=O(f(n))。
四、举例总结：
一般来说，时间复杂度和空间复杂度还是比较难理解的。我们这里举例总结一下：
下面我们来举一个例子说明一下；看如下代码：
for（i=1;i<=n;++i{
for(j=1;j<=n;++j) {
c[ i ][ j ]=0; //基本单元 执行次数是n^2
for(k=1;k<=n;++k)
c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //基本单元 执行次数是n^3(可以认为是三个for循环）
}
}
此时T(n)= n^2+n^3，我们这里取大的n^3（最大）作为T(n)的同数量级，则f(n)=n^3。因为T(n)/f(n)求极限可以得到常数C，则根据T(n)=O(f(n))=O(n^3)；
一般情况下，随着输入规模n的增大，T(n)增长最慢的算法为最优算法。
常见排序算法复杂度