算法复杂度

时间复杂度

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

存在不确定n，在if、while、do-while、foreach等这样循环内，有多层嵌套时时间复杂度就越高。

for($i = 1; $i<=$n; $i++){
    for($j = 0; $j<$i; $j++){
        print($i.'_'.$j);
    }
}

这个的时间复杂度为T(n) = O(n^2)

那是怎么得来的呢？

1 + 2 + 3 + 4 + 5 + ... + n = (n^2 + n)/2

由于时间复杂度不考虑系数，所以近似于n^2

$x=91; $y=100;
while($y > 0){
    if ($x > 100){
        $x -= 10;
        $y--;
    } else {
        $x++;
    }
}

上面的时间复杂度是T(n) = O(1)，是常阶函数

因为都是确定值

算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关

在数值A[0..n-1]中查找给定值K的算法大致如下：

$i = $n - 1;
$k = 8;
while($i >= 0 && $A[$i] != $k){
    $i--;
}

此算法中的频度不仅与问题规模n有关，还与输入实例中A的各元素取值及K的取值有关: ①若A中没有与K相等的元素，则算法的频度f(n)=n； ②若A的最后一个元素等于K,则算法的频度f(n)是常数0。

有两个算法A1和A2求解同一问题，时间复杂度分别是T1(n)=100n^2，T2(n)=5n3。（1）当输入量n＜20时，有T1(n)＞T2(n)，后者花费的时间较少。（2）随着问题规模n的增大，两个算法的时间开销之比5n^3 / 100n^2=n/20亦随着增大。即当问题规模较大时，算法A1比算法A2要有效地多。它们的渐近时间复杂度O(n2)和O(n3)从宏观上评价了这两个算法在时间方面的质量。在算法分析时，往往对算法的时间复杂度和渐近时间复杂度不予区分，而经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度

空间复杂度

空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作:

S(n)=O(f(n))

算法执行期间所需要的存储空间包括3个部分：

1、算法程序所占的空间；

2、输入的初始数据所占的存储空间；

3、算法执行过程中所需要的额外空间。