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

来自计算思维百科
跳转至: 导航搜索
第3行: 第3行:
 
== 概念 ==
 
== 概念 ==
  
 设算法的执行时间 为[[File:|29x20px]] ,如果存 在[[File:|35x22px]] ,使得:
+
 设算法的执行时间 为T(n) ,如果存 在T<sup>*</sup>(n) ,使得:
  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; [[File:|117x42px]]
+
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &#x5B;&#x5B;File:|117x42px&#x5D;&#x5D;
  
 就 称[[File:|35x22px]] 为算法的渐进时间复杂度。
+
 就 称T<sup>*</sup>(n) 为算法的渐进时间复杂度。
  
 通常算法的时间复杂度是指算法的渐进时间复杂度,仍记为[[File:|29x20px]] 。它忽略了运行时间的低阶项和高阶项系数,只关心运行时间的高阶项。
+
 通常算法的时间复杂度是指算法的渐进时间复杂度,仍记为&#x5B;&#x5B;File:|29x20px&#x5D;&#x5D; 。它忽略了运行时间的低阶项和高阶项系数,只关心运行时间的高阶项。
  
 
== 时间复杂度的级别 ==
 
== 时间复杂度的级别 ==
第17行: 第17行:
 
 常见复杂度中的前六项称为多项式时间复杂度,后两项称为指数时间复杂度。两者有何不同?
 
 常见复杂度中的前六项称为多项式时间复杂度,后两项称为指数时间复杂度。两者有何不同?
  
 我们知道,指数函数比多项式函数增长的快很多。这导致:多项式时间复杂度的算法,通过提高计算机速度,可提高解题规模;但指数时间复杂度的算法,即使提高计算机速度,也不能增加解题规模。以Fibonacci数列递归算法为例,它是指数时间复杂度(分析见后面)。用2002年世界上最快超级计算机NEC Earth Simulator计算[[File:|28x24px]] 将至少需要[[File:|23x20px]] 秒,2008年世界上的最快超级计算机IBM Roadrunner比NEC Earth Simulator快近30倍,但用相同时间计算Fibonacci数列,也只能多计算7个数。
+
 我们知道,指数函数比多项式函数增长的快很多。这导致:多项式时间复杂度的算法,通过提高计算机速度,可提高解题规模;但指数时间复杂度的算法,即使提高计算机速度,也不能增加解题规模。以Fibonacci数列递归算法为例,它是指数时间复杂度(分析见后面)。用2002年世界上最快超级计算机NEC Earth Simulator计算<span style="font-size:medium;">F<sub>200</sub></span> 将至少需要<span style="font-size:medium;">2<sup>92</sup></span> 秒,2008年世界上的最快超级计算机IBM Roadrunner比NEC Earth Simulator快近30倍,但用相同时间计算Fibonacci数列,也只能多计算7个数。
  
 
 研究一个问题,追求的是其多项式时间的算法。现在还有很多问题没找到其多项式时间的算法,如旅行商问题等,这就是第一章介绍的NPC问题,也称难解的问题。
 
 研究一个问题,追求的是其多项式时间的算法。现在还有很多问题没找到其多项式时间的算法,如旅行商问题等,这就是第一章介绍的NPC问题,也称难解的问题。
第25行: 第25行:
 
== 时间复杂度的记号 ==
 
== 时间复杂度的记号 ==
  
=== 运行时间的上界 ,O 记号 ===
+
=== 运行时间的上界 ,Ο 记号 ===
  
  令[[File:|16x16px]] 为自然数集合 ,[[File:|19x19px]] 为正实数集合。函 数[[File:|69x20px]],函数g:[[File:|49x20px]] ,若存在自然数[[File:|17x24px]] 和正常数c,使得对所有的[[File:|37x20px]],都有[[File:|74x20px]] ,就称函数[[File:|36x21px]] 的阶至多是[[File:|57x21px]]
+
  令N 为自然数集合 ,R<sub>+</sub> 为正实数集合。函 数f:N→R<sub>+</sub>,函数g:N→R<sub>+</sub> ,若存在自然数<span style="font-size:medium;">n<sub>0</sub></span> 和正常数c,使得对所有的<span style="font-size:large;">n</span><span style="font-size:smaller;">≥</span><span style="font-size:large;">n<sub>0</sub></span>,都有<span style="font-size:medium;">f(n)</span><span style="font-size:smaller;">≤</span><span style="font-size:medium;">cg(n)</span> ,就称函数<span style="font-size:medium;">f(n)</span> 的阶至多是<span style="font-size:medium;">Ο</span>(<span style="font-size:medium;">g(n))</span>
  
 上界表明:[[File:|36x21px]] 的增长最多像[[File:|35x21px]] 的增长那样快。
+
 上界表明:<span style="font-size:medium;">f(n)</span> 的增长最多像<span style="font-size:medium;">g(n)</span> 的增长那样快。
  
=== 运行时间的下界,[[File:|17x17px]] 记号 ===
+
=== 运行时间的下界, Ω 记号 ===
  
  令[[File:|16x16px]] 为自然数集合 ,[[File:|19x19px]] 为正实数集合。函 数[[File:|69x20px]],函数g:[[File:|49x20px]] ,若存在自然数[[File:|17x24px]] 和正常数c,使得对所有的[[File:|41x24px]],都有[[File:|74x20px]] ,就称函数[[File:|36x21px]] 的阶至少是[[File:|49x20px]]
+
  令N 为自然数集合 ,R<sub>+</sub> 为正实数集合。函 数f:N→R<sub>+</sub>,函数g:N→R<sub>+</sub> ,若存在自然数<span style="font-size:medium;">n<sub>0</sub></span> 和正常数c,使得对所有的<span style="font-size:large;">n</span><span style="font-size:smaller;">≥</span><span style="font-size:large;">n<sub>0</sub></span>,都有<span style="font-size:medium;">f(n)</span><span style="font-size:smaller;">≥</span><span style="font-size:medium;">cg(n)</span> ,就称函数<span style="font-size:medium;">f(n)</span> 的阶至少是<span style="font-size:medium;">Ω</span>(<span style="font-size:medium;">g(n))</span>
  
 下界表明:[[File:|36x21px]] 的增长至少像[[File:|35x21px]] 的增长那样快。
+
 下界表明:<span style="font-size:medium;">f(n)</span> 的增长至少像<span style="font-size:medium;">g(n)</span> 的增长那样快。
  
=== 运行时间的准确界,[[File:|17x19px]] 记号 ===
+
=== 运行时间的准确界, Θ 记号 ===
  
  令[[File:|16x16px]] 为自然数集合 ,[[File:|19x19px]] 为正实数集合。函 数[[File:|69x20px]],函数g:[[File:|49x20px]] ,若存在自然数[[File:|17x24px]] 和两个正常 数[[File:|62x20px]] ,使得对所有的[[File:|37x20px]],都有[[File:|130x20px]] ,就称函数[[File:|30x18px]] 的阶是[[File:|48x20px]]
+
  令N 为自然数集合 ,R<sub>+</sub> 为正实数集合。函 数f:N→R<sub>+</sub>,函数g:N→R<sub>+</sub>, ,若存在自然数<span style="font-size:medium;">n<sub>0</sub></span> 和两个正常 数0<span style="font-size:smaller;">≤</span><span style="font-size:large;">c<sub>1</sub></span><span style="font-size:smaller;">≤​</span><span style="font-size:large;"><sub></sub>c<sub>2</sub></span> ,使得对所有的<span style="font-size:large;">n</span><span style="font-size:smaller;">≥</span><span style="font-size:large;">n<sub>0</sub></span>,都有<span style="font-size:large;">c<sub>1</sub></span><span style="font-size:medium;">g(n)</span><span style="font-size:smaller;">≤</span><span style="font-size:medium;">f(n)</span><span style="font-size:smaller;">≤</span><span style="font-size:large;">c<sub>2</sub></span><span style="font-size:medium;">g(n)</span> ,就称函数<span style="font-size:medium;">f(n)</span> 的阶是<span style="font-size:medium;">Θ</span>(<span style="font-size:medium;">g(n))</span>
  
 准确界表明:[[File:|30x18px]] 的增长和[[File:|29x18px]] 的增长一样快。
+
 准确界表明:<span style="font-size:medium;">f(n)</span> 的增长和<span style="font-size:medium;">g(n)</span> 的增长一样快。
  
 通常分析的是算法的最坏时间复杂度,所以常见的是O记号。<br/>
+
 通常分析的是算法的最坏时间复杂度,所以常见的是O记号。
  
 
== 非递归算法的时间复杂度分析 ==
 
== 非递归算法的时间复杂度分析 ==
第116行: 第116行:
 
 第一趟:将40插入到10中,大于10,插入10之前,已排序元素为:
 
 第一趟:将40插入到10中,大于10,插入10之前,已排序元素为:
  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 40 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 10
+
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 40 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;10
  
 
 第二趟:将30插入到40 10中,30大于10、小于40,插入40之后,已排序元素为:
 
 第二趟:将30插入到40 10中,30大于10、小于40,插入40之后,已排序元素为:
第124行: 第124行:
 
 第三趟:将5插入到40 30 10中,小于10,插入10之后,已排序元素为:
 
 第三趟:将5插入到40 30 10中,小于10,插入10之后,已排序元素为:
  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; 40 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 30 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 10 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 5
+
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 40 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;30 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 10 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 5
  
 
 最好情况分析:最好情况是初始数据已按序排列。这种情况下,插入<span style="font-size:large;">a</span><sub>i</sub>''','''只需与'''<!--[if gte vml 1]><v:shapetype
 
 最好情况分析:最好情况是初始数据已按序排列。这种情况下,插入<span style="font-size:large;">a</span><sub>i</sub>''','''只需与'''<!--[if gte vml 1]><v:shapetype

2015年10月23日 (五) 02:05的版本

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

概念

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

                                                        [[File:|117x42px]]

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

通常算法的时间复杂度是指算法的渐进时间复杂度,仍记为[[File:|29x20px]]。它忽略了运行时间的低阶项和高阶项系数,只关心运行时间的高阶项。

时间复杂度的级别

按数量级递增排列,常见的复杂度阶有: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的通项公式是:

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

   

是指数时间复杂度。                                                            

从时间复杂度来讲,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个插入位置,如图3-10所示。




                            图3-10 ai的插入位置图

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

                         

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


因为:


所以:


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

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