算法复杂度

算法复杂度

分为时间复杂度和空间复杂度。即算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。

时间复杂度

在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。

时间复杂度计算方法

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，去掉与这个最高阶相乘的常数得到时间复杂度

空间复杂度

算法程序所占用的空间

输入的数据所占存储空间

执行过程所需额外空间