“时间复杂度”的版本间的差异

来自计算思维百科
跳转至: 导航搜索
第173行: 第173行:
 
 每个位置插入概率相等,为1/i。插入第1个位置需循环比较i-1次,插入第j(2≤j≤i)个位置需循环比较i-j+1次。故插入<span style="font-size:large;">a</span>i的平均循环次数Ti为:
 
 每个位置插入概率相等,为1/i。插入第1个位置需循环比较i-1次,插入第j(2≤j≤i)个位置需循环比较i-j+1次。故插入<span style="font-size:large;">a</span>i的平均循环次数Ti为:
  
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [[File:9.3.5.png]]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
+
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [[File:9.3.5.png|RTENOTITLE]]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
  
 
 分别将<span style="font-size:large;">a</span><span style="font-size:medium;"><sub>2</sub>,</span><span style="font-size:large;">a</span><span style="font-size:medium;"><sub>3</sub>,…,</span><span style="font-size:large;">a</span><sub><span style="font-size:medium;">n</span></sub>插入,所需平均循环总次数T(n)为:
 
 分别将<span style="font-size:large;">a</span><span style="font-size:medium;"><sub>2</sub>,</span><span style="font-size:large;">a</span><span style="font-size:medium;"><sub>3</sub>,…,</span><span style="font-size:large;">a</span><sub><span style="font-size:medium;">n</span></sub>插入,所需平均循环总次数T(n)为:
  
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[[File:9.3.6.png]]
+
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[[File:9.3.6.png|RTENOTITLE]]
  
 +
因为: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
  
 +
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[[File:9.3.7.png|RTENOTITLE]]
  
因为:
+
 所以: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
 
 
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[[File:9.3.7.png]]
 
 
 
 
 
 
 
 所以:
 
 
 
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;[[File:9.3.8.png]]
 
 
 
  
 +
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[[File:9.3.8.png|RTENOTITLE]]
  
 
 得到插入排序平均情况下的时间复杂性是<span style="font-size:large;">O(n<sup>2</sup>)</span>
 
 得到插入排序平均情况下的时间复杂性是<span style="font-size:large;">O(n<sup>2</sup>)</span>
  
 
 因插入排序的运行时间介于最好情况与最坏情况之间,用界符号表示有:插入排序的时间复杂度上界为<span style="font-size:large;">O(n<sup>2</sup>)</span>(最坏情况),时间复杂度下界为Ω(n)(最好情况)。两者不同阶,不能用准确界表示插入排序的时间复杂度。
 
 因插入排序的运行时间介于最好情况与最坏情况之间,用界符号表示有:插入排序的时间复杂度上界为<span style="font-size:large;">O(n<sup>2</sup>)</span>(最坏情况),时间复杂度下界为Ω(n)(最好情况)。两者不同阶,不能用准确界表示插入排序的时间复杂度。

2015年10月23日 (五) 04:52的版本

算法的时间复杂度'('Time Complexity)度量算法的运行时间。

概念

设算法的执行时间为T(n),如果存在T*(n),使得:

                              RTENOTITLE

就称T*(n)为算法的渐进时间复杂度。

通常算法的时间复杂度是指算法的渐进时间复杂度,仍记为T(n)。它忽略了运行时间的低阶项和高阶项系数,只关心运行时间的高阶项。

时间复杂度的级别

按数量级递增排列,常见的复杂度阶有:1、log2n、n、nlog2n、n2、n3、2n、n!等。时间复杂度函数的阶越小,算法运行时间越短;反之越长。

常见复杂度中的前六项称为多项式时间复杂度,后两项称为指数时间复杂度。两者有何不同?

我们知道,指数函数比多项式函数增长的快很多。这导致:多项式时间复杂度的算法,通过提高计算机速度,可提高解题规模;但指数时间复杂度的算法,即使提高计算机速度,也不能增加解题规模。以Fibonacci数列递归算法为例,它是指数时间复杂度(分析见后面)。用2002年世界上最快超级计算机NEC Earth Simulator计算F200将至少需要292秒,2008年世界上的最快超级计算机IBM Roadrunner比NEC Earth Simulator快近30倍,但用相同时间计算Fibonacci数列,也只能多计算7个数。

研究一个问题,追求的是其多项式时间的算法。现在还有很多问题没找到其多项式时间的算法,如旅行商问题等,这就是第一章介绍的NPC问题,也称难解的问题。

有时算法的运行时间并不是一个准确的函数,它在某个范围之内。

时间复杂度的记号

运行时间的上界,Ο记号

令N为自然数集合,R+为正实数集合。函数f:N→R+,函数g:N→R+,若存在自然数n0和正常数c,使得对所有的nn0,都有f(n)cg(n),就称函数f(n)的阶至多是Ο(g(n))

上界表明:f(n)的增长最多像g(n)的增长那样快。

运行时间的下界,Ω记号

令N为自然数集合,R+为正实数集合。函数f:N→R+,函数g:N→R+,若存在自然数n0和正常数c,使得对所有的nn0,都有f(n)cg(n),就称函数f(n)的阶至少是Ω(g(n))

下界表明:f(n)的增长至少像g(n)的增长那样快。

运行时间的准确界,Θ记号

令N为自然数集合,R+为正实数集合。函数f:N→R+,函数g:N→R+,,若存在自然数n0和两个正常数0c1≤​c2,使得对所有的nn0,都有c1g(n)f(n)c2g(n),就称函数f(n)的阶是Θ(g(n))

准确界表明:f(n)的增长和g(n)的增长一样快。

通常分析的是算法的最坏时间复杂度,所以常见的是O记号。

非递归算法的时间复杂度分析

非递归算法常用的时间复杂度分析方法是循环次数统计法。 算法的运行时间常和算法中的循环次数成正比,而循环次数又依赖于算法的输入数据规模。因此,对算法中的循环次数进行统计,可以很好地表示算法的运行时间。如n钱买n鸡问题,对x,y,z分别进行循环,x的循环次数最多是:n/5,y的循环次数最多是n/3,z的循环次数最多是:n/3,总循环次数为(n/5)*(n/3)*(n/3)。因此,该问题的时间复杂度为O(n3),与上述分析一致。

分析动态规划求Fibonacci序列的时间复杂度。

动态规划法求Fib序列第n项的伪代码为:

Fib(n)

1 F[1]←F[2]←1

2 FOR i=3 to n

3   DO F[i]← F[i-1]+F[i-2]

4 RETURN F[n]


递归算法的时间复杂度分析

递归算法和分治算法中,都用到了递归思想。大问题的求解依赖于子问题的求解,因此它们的时间复杂度T(n)可用自身表示,即得到关于T(n)的递归方程。

分析Fibonacci序列递归算法的时间复杂度。

根据算法3.5可知,该算法的伪代码描述为:

Fib(n)                             

1  IF n≤2

2    THEN RETURN 1                      

3  RETURN Fib(n-1)+Fib(n-2)  

设递归计算第n项的运行时间为T(n)。根据算法描述,当n≤2时,T(n)的计算时间是常数值,T(1)=T(2)=1;当n>2时,计算Fn,需先计算Fn-1、Fn-2,再加判定等其它操作,得到T(n)=T(n-1)+T(n-2)+2。

因此,T(n)的递归方程为:

                           T(n)=1             n≤2

                           T(n)=T(n-1)+T(n-2)+2   n>2

    显然,T(n)≥Fn,而Fn的通项公式是:

                            RTENOTITLE

故Fibonacci序列递归算法的时间复杂度下界是:

                           RTENOTITLE

是指数时间复杂度。                                                            

从时间复杂度来讲,Fibonacci数列的动态规划算法优于递归算法。

最好、最坏、平均情况时间复杂度分析

有时算法的运行时间,不仅与问题规模有关,还与初始数据相关。这种情况下,需要分析算法的最好情况、最坏情况、平均情况的时间复杂度。

以插入排序为例分析。

设初始数据a1,a2,…,an,插入排序的实现思想是:

  1. 初始a1已排好序;
  2. 若前面i-1个元素已排序,ai依次与ai-1,ai-2,…a1比较,插入适当位置,完成ai的排序,i=2,3,…n。

假设对数据10 40 30 5降序排序,插入排序的计算过程为:

初始:只有10排好序。

第一趟:将40插入到10中,大于10,插入10之前,已排序元素为:

                40                  10

第二趟:将30插入到40 10中,30大于10、小于40,插入40之后,已排序元素为:

                40              30             10

第三趟:将5插入到40 30 10中,小于10,插入10之后,已排序元素为:

                    40                  30             10             5

最好情况分析:最好情况是初始数据已按序排列。这种情况下,插入ai只需与'ai-1比较,插入'ai-1之后。之后。分析时间复杂度,循环插入数据n-1个,每插入一个数据,只需比较1次,因此插入排序最好情况的时间复杂度为O(n)。 

最坏情况分析:最坏情况是初始数据完全逆序排列。这种情况下,插入ai需依次与ai-1,ai-2,…,a1a1之前。分析时间复杂度,循环插入数据n-1个,插入ai(i=2,…,n),需循环比较i-1次。因此,插入排序最坏情况的总循环次数为1+2+…+n-1,时间复杂度为O(n2)

平均情况分析:算法的平均情况时间分析是取所有可能输入的平均运行时间。此时,需要考虑所有输入的概率问题。

假设前i-1个元素已排序好,ai有i个插入位置,如图1所示。                                                                                                 

            RTENOTITLE

                        图1 ai的插入位置图

每个位置插入概率相等,为1/i。插入第1个位置需循环比较i-1次,插入第j(2≤j≤i)个位置需循环比较i-j+1次。故插入ai的平均循环次数Ti为:

                RTENOTITLE         

分别将a2,a3,…,an插入,所需平均循环总次数T(n)为:

               RTENOTITLE

因为:              

                 RTENOTITLE

所以:              

                 RTENOTITLE

得到插入排序平均情况下的时间复杂性是O(n2)

因插入排序的运行时间介于最好情况与最坏情况之间,用界符号表示有:插入排序的时间复杂度上界为O(n2)(最坏情况),时间复杂度下界为Ω(n)(最好情况)。两者不同阶,不能用准确界表示插入排序的时间复杂度。