算法复杂度
分为时间复杂度和空间复杂度。即算法在编写成可执行程序后,运行时所需要的资源,资源包括时间资源和内存资源。
时间复杂度
在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。
时间复杂度计算方法
1、一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。
分析:随着模块n的增大,算法执行的时间的增长率和 f(n) 的增长率成正比,所以 f(n) 越小,算法的时间复杂度越低,算法的效率越高
2、在计算时间复杂度的时候,先找出算法的基本操作,然后根据相应的各语句确定它的执行次数,再找出 T(n) 的同数量级(它的同数量级有以下:1,log2n,n,n log2n ,n的平方,n的三次方,2的n次方,n!),找出后,f(n) = 该数量级,若 T(n)/f(n) 求极限可得到一常数c,则时间复杂度T(n) = O(f(n))
例:算法:
for(i=1; i<=n; ++i)
{
for(j=1; j<=n; ++j)
{
A=123;//该步骤属于基本操作执行次数:n的平方次
for(k=1; k<=n; ++k)
A++;//该步骤属于基本操作执行次数:n的三次方次
}
}
则有 T(n) = n 的平方+n的三次方,根据上面括号里的同数量级,我们可以确定 n的三次方 为T(n)的同数量级
则有 f(n) = n的三次方,然后根据 T(n)/f(n) 求极限可得到常数c
则该算法的时间复杂度:T(n) = O(n3) 注:n3即是n的3次方。
时间复杂度分类 1 < log2n < n < n*log2n < n2 < n3 < 2n < 3n < n! (1是一个常量)。
算法效率依次降低
时间复杂度为log2n例子
$a = 1;
$n = 1000;
while($a < $n) {
$a*=2;
echo $a;
}
计算时间复杂度
1.去掉运行时间中的所有加法常数。
2.只保留最高阶项。
3.如果最高阶项存在且不是1,去掉与这个最高阶相乘的常数得到时间复杂度
排序法 | 最差时间分析 | 平均时间复杂度 | 稳定度 | 空间复杂度 |
---|---|---|---|---|
冒泡排序 | O(n2) | O(n2) | 稳定 | O(1) |
快速排序 | O(n2) | O(n*log2n) | 不稳定 | O(log2n)~O(n) |
选择排序 | O(n2) | O(n2) | 稳定 | O(1) |
二叉树排序 | O(n2) | O(n*log2n) | 不稳定 | O(n) |
插入排序 | O(n2) | O(n2) | 稳定 | O(1) |
堆排序 | O(n*log2n) | O(n*log2n) | 不稳定 | O(1) |
空间复杂度
算法程序所占用的空间
输入的数据所占存储空间
执行过程所需额外空间