PHP算法大全(1)基础篇-时间复杂度和空间复杂度

2017-03-10 09:35:07 admin ...

前言:

提到算法,必然会讨论算法复杂度。不少非计算机专业的程序员在参与算法讨论时,多少会有点尴尬(算法复杂度到底是个什么东西)。

内容概要:

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)增长最慢的算法为最优算法。


常见排序算法复杂度

相似文章


345708673

在路上

技术无止境,一直在路上。 年过而立,惴惴不安,愈加发奋,孜孜求学。