关于时间复杂度~

时间:2022-06-26 17:10:35

首先:借鉴前人大佬!感谢!本文只做整理

http://www.matrix67.com/blog/archives/105

 

首先在文中介绍了时间复杂度O,本身自己对于这个有所遗忘,并且本身在算法课上学的不咋地,正好借此梳理一下。

下面给出百度百科关于时间复杂的定义:

在计算机科学中,算法的时间复杂度是一个函数,它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。

百度百科关于时间复杂度的计算方法:

一般,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得T(n)/f(n)的极限值(当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)
    {
        c[i][j] = 0;//该步骤属于基本操作执行次数:n的平方次
        for(k=1; k<=n; ++k)
            c[i][j] += a[i][k] * b[k][j];//该步骤属于基本操作执行次数:n的三次方次
    }
}
 
则有  关于时间复杂度~  ,根据上面括号里的同数量级,我们可以确定 n的三次方 为T(n)的同数量级则有
  关于时间复杂度~ 
,然后根据 T(n)/f(n) 求极限可得到常数c则该算法的时间复杂度:T(n) = O(n^3) 注:n^3即是n的3次方。
3.在pascal中比较容易理解,容易计算的方法是:看看有几重for循环,只有一重则时间复杂度为O(n),二重则为O(n^2),依此类推,如果有二分则为O(logn),二分例如快速幂、二分查找,如果一个for循环套一个二分,那么时间复杂度则为O(nlogn)。

引文中给出了如下的解释,我觉得受益良多。

时间复杂度不是表示程序解决一个问题所花费的时间,而是表示,当问题规模扩大后,程序需要的时间长度增长有多快。也就是,对于计算机,处理某一个特定数据的效率不能衡量程序的好坏,而应该看这个数据规模扩大到数百倍后程序的运行时间是否一样?或者是否变慢了?

不管数据多大,程序处理画的时间始终是那么多的,我们就说这个程序时好的,具有O(1)的时间复杂度,称常数级复杂度。数据规模变得多大,花的时间变得多长,这个程序的复杂度就是O(n),比如找N个数中最大的;而像冒泡排序、插入排序等,数据扩大2倍,时间变慢4倍的,属于O(n^2)的复杂度。还有一些穷举类的算法,所需时间长度成几何阶数上涨,这就是O(a^n)的指数级复杂度,甚至O(n!)的阶乘级复杂度。不会存在O(2*n^2)的复杂度,因为前面的那个“2”是系数,根本不会影响到整个程序的时间增长。同样地,O (n^3+n^2)的复杂度也就是O(n^3)的复杂度。因此,我们会说,一个O(0.01*n^3)的程序的效率比O(100*n^2)的效率低,尽管在n很小的时候,前者优于后者,但后者时间随数据规模增长得慢,最终O(n^3)的复杂度将远远超过O(n^2)。我们也说,O(n^100)的复杂度小于O(1.01^n)的复杂度。

容易看出,前面的几类复杂度被分为两种级别,其中后者的复杂度无论如何都远远大于前者:一种是O(1),O(log(n)),O(n^a)等,我们把它叫做多项式级的复杂度,因为它的规模n出现在底数的位置;另一种是O(a^n)和O(n!)型复杂度,它是非多项式级的,其复杂度计算机往往不能承受。当我们在解决一个问题时,我们选择的算法通常都需要是多项式级的复杂度,非多项式级的复杂度需要的时间太多,往往会超时,除非是数据规模非常小。