时间复杂度
一般情况下,算法中基本操作重复执行的次数是问题规模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)=100n2,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、算法执行过程中所需要的额外空间。