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

来自计算思维百科
跳转至: 导航搜索
第1行: 第1行:
算法的''' 时间复杂度''''''(''''''Time Complexity)''' 度量算法的运行时间。
+
<p> 算法的<b> 时间复杂度'</b><i>('</i><b>Time Complexity)</b> 度量算法的运行时间。
 
+
</p>
== 概念 ==
+
<h2> 概念 </h2>
 
+
<p> 设算法的执行时间为T(n),如果存在T<sup>*</sup>(n),使得:
设算法的执行时间为T(n),如果存在T<sup>*</sup>(n),使得:
+
</p><p>&#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160;&#160;<img src="/nhpccwiki/images/d/d5/9.3.1.png" _fck_mw_filename="9.3.1.png" _fck_mw_origimgwidth="118" _fck_mw_origimgheight="43" alt="RTENOTITLE" title="RTENOTITLE" style="vertical-align:middle;" />
 
+
</p><p> 就称T<sup>*</sup>(n)为算法的渐进时间复杂度。
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;[[File:9.3.1.png|RTENOTITLE]]
+
</p><p> 通常算法的时间复杂度是指算法的渐进时间复杂度,仍记为T(n)。它忽略了运行时间的低阶项和高阶项系数,只关心运行时间的高阶项。
 
+
</p>
就称T<sup>*</sup>(n)为算法的渐进时间复杂度。
+
<h2> 时间复杂度的级别 </h2>
 
+
<p> 按数量级递增排列,常见的复杂度阶有:1、log<sub>2</sub>n、n、nlog<sub>2</sub>n、n<sup>2</sup>、n<sup>3</sup>、2<sup>n</sup>、n!等。时间复杂度函数的阶越小,算法运行时间越短;反之越长。
通常算法的时间复杂度是指算法的渐进时间复杂度,仍记为T(n)。它忽略了运行时间的低阶项和高阶项系数,只关心运行时间的高阶项。
+
</p><p> 常见复杂度中的前六项称为多项式时间复杂度,后两项称为指数时间复杂度。两者有何不同?
 
+
</p><p> 我们知道,指数函数比多项式函数增长的快很多。这导致:多项式时间复杂度的算法,通过提高计算机速度,可提高解题规模;但指数时间复杂度的算法,即使提高计算机速度,也不能增加解题规模。以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个数。
== 时间复杂度的级别 ==
+
</p><p> 研究一个问题,追求的是其多项式时间的算法。现在还有很多问题没找到其多项式时间的算法,如旅行商问题等,这就是第一章介绍的NPC问题,也称难解的问题。
 
+
</p><p> 有时算法的运行时间并不是一个准确的函数,它在某个范围之内。
按数量级递增排列,常见的复杂度阶有:1、log<sub>2</sub>n、n、nlog<sub>2</sub>n、n<sup>2</sup>、n<sup>3</sup>、2<sup>n</sup>、n!等。时间复杂度函数的阶越小,算法运行时间越短;反之越长。
+
</p>
 
+
<h2> 时间复杂度的记号 </h2>
常见复杂度中的前六项称为多项式时间复杂度,后两项称为指数时间复杂度。两者有何不同?
+
<h3> 运行时间的上界,Ο记号 </h3>
 
+
<p> 令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>。
我们知道,指数函数比多项式函数增长的快很多。这导致:多项式时间复杂度的算法,通过提高计算机速度,可提高解题规模;但指数时间复杂度的算法,即使提高计算机速度,也不能增加解题规模。以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个数。
+
</p><p> 上界表明:<span style="font-size:medium;">f(n)</span>的增长最多像<span style="font-size:medium;">g(n)</span>的增长那样快。
 
+
</p>
研究一个问题,追求的是其多项式时间的算法。现在还有很多问题没找到其多项式时间的算法,如旅行商问题等,这就是第一章介绍的NPC问题,也称难解的问题。
+
<h3> 运行时间的下界,Ω记号 </h3>
 
+
<p> 令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>。
有时算法的运行时间并不是一个准确的函数,它在某个范围之内。
+
</p><p> 下界表明:<span style="font-size:medium;">f(n)</span>的增长至少像<span style="font-size:medium;">g(n)</span>的增长那样快。
 
+
</p>
== 时间复杂度的记号 ==
+
<h3> 运行时间的准确界,Θ记号 </h3>
 
+
<p> 令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;">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>。
=== 运行时间的上界,Ο记号 ===
+
</p><p>准 确界表明:<span style="font-size:medium;">f(n)</span>的增长和<span style="font-size:medium;">g(n)</span>的增长一样快。
 
+
</p><p> 通常分析的是算法的最坏时间复杂度,所以常见的是O记号。
令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>。
+
</p>
 
+
<h2> 非递归算法的时间复杂度分析 </h2>
上界表明:<span style="font-size:medium;">f(n)</span>的增长最多像<span style="font-size:medium;">g(n)</span>的增长那样快。
+
<p> 非递归算法常用的时间复杂度分析方法是循环次数统计法。 算法的运行时间常和算法中的循环次数成正比,而循环次数又依赖于算法的输入数据规模。因此,对算法中的循环次数进行统计,可以很好地表示算法的运行时间。如n钱买n鸡问题,对x,y,z分别进行循环,x的循环次数最多是:n/5,y的循环次数最多是n/3,z的循环次数最多是:n/3,总循环次数为(n/5)*(n/3)*(n/3)。因此,该问题的时间复杂度为<span style="font-size:large;">O(n<sup>3</sup>)</span>,与上述分析一致。
 
+
</p>
=== 运行时间的下界,Ω记号 ===
+
<h3> 分析动态规划求Fibonacci序列的时间复杂度。 </h3>
 
+
<p> 动态规划法求Fib序列第n项的伪代码为:
令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>。
+
</p><p>Fib(n)
 
+
</p><p>1&#160;F[1]←F[2]←1
下界表明:<span style="font-size:medium;">f(n)</span>的增长至少像<span style="font-size:medium;">g(n)</span>的增长那样快。
+
</p><p>2&#160;FOR i=3 to n
 
+
</p><p>3&#160;&#160;&#160;DO&#160;F[i]← F[i-1]+F[i-2]
=== 运行时间的准确界,Θ记号 ===
+
</p><p>4&#160;RETURN F[n]
 
+
</p><p>
令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;">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>。
+
</p>
 
+
<h2> 递归算法的时间复杂度分析 </h2>
确界表明:<span style="font-size:medium;">f(n)</span>的增长和<span style="font-size:medium;">g(n)</span>的增长一样快。
+
<p> 递归算法和分治算法中,都用到了递归思想。大问题的求解依赖于子问题的求解,因此它们的时间复杂度T(n)可用自身表示,即得到关于T(n)的递归方程。
 
+
</p>
通常分析的是算法的最坏时间复杂度,所以常见的是O记号。
+
<h3> 分析Fibonacci序列递归算法的时间复杂度。 </h3>
 
+
<p> 根据算法3.5可知,该算法的伪代码描述为:
== 非递归算法的时间复杂度分析 ==
+
</p><p>Fib(n)&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;
 
+
</p><p>1&#160; IF n≤2
非递归算法常用的时间复杂度分析方法是循环次数统计法。 算法的运行时间常和算法中的循环次数成正比,而循环次数又依赖于算法的输入数据规模。因此,对算法中的循环次数进行统计,可以很好地表示算法的运行时间。如n钱买n鸡问题,对x,y,z分别进行循环,x的循环次数最多是:n/5,y的循环次数最多是n/3,z的循环次数最多是:n/3,总循环次数为(n/5)*(n/3)*(n/3)。因此,该问题的时间复杂度为<span style="font-size:large;">O(n<sup>3</sup>)</span>,与上述分析一致。
+
</p><p>2 &#160; &#160;THEN RETURN 1&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;
 
+
</p><p>3&#160; RETURN Fib(n-1)+Fib(n-2)&#160;&#160;
=== 分析动态规划求Fibonacci序列的时间复杂度。 ===
+
</p><p> 设递归计算第n项的运行时间为T(n)。根据算法描述,当n≤2时,T(n)的计算时间是常数值,T(1)=T(2)=1;当n&gt;2时,计算F<sub>n</sub>,需先计算F<sub>n-1</sub>、F<sub>n-2</sub>,再加判定等其它操作,得到T(n)=T(n-1)+T(n-2)+2。
 
+
</p><p> 因此,T(n)的递归方程为:
动态规划法求Fib序列第n项的伪代码为:
+
</p><p>&#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160;<span style="font-size:large;">T</span>(n)=1 &#160; &#160; &#160; &#160; &#160; &#160;&#160;<span style="font-size:large;">n≤2</span>
 
+
</p><p>&#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160;<span style="font-size:large;">T</span>(n)=<span style="font-size:large;">T</span>(n-1)+<span style="font-size:large;">T(</span>n-2)+2 &#160; <span style="font-size:large;">n&gt;2</span>
Fib(n)
+
</p><p>&#160;&#160;&#160; 显然,T(n)≥F<sub>n</sub>,而F<sub>n</sub>的通项公式是:
 
+
</p><p>&#160;&#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160;<img src="/nhpccwiki/images/b/bc/9.3.2.png" _fck_mw_filename="9.3.2.png" _fck_mw_origimgwidth="196" _fck_mw_origimgheight="48" alt="RTENOTITLE" title="RTENOTITLE" style="vertical-align:middle;" />
1&nbsp;F[1]←F[2]←1
+
</p><p> 故Fibonacci序列递归算法的时间复杂度下界是:
 
+
</p><p>&#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160;<img src="/nhpccwiki/images/9/94/9.3.3.png" _fck_mw_filename="9.3.3.png" _fck_mw_origimgwidth="194" _fck_mw_origimgheight="58" alt="RTENOTITLE" title="RTENOTITLE" style="vertical-align:middle;" />
2&nbsp;FOR i=3 to n
+
</p><p> 是指数时间复杂度。 &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160;
 
+
</p><p> 从时间复杂度来讲,Fibonacci数列的动态规划算法优于递归算法。
3&nbsp;&nbsp;&nbsp;DO&nbsp;F[i]← F[i-1]+F[i-2]
+
</p>
 
+
<h2> 最好、最坏、平均情况时间复杂度分析 </h2>
4&nbsp;RETURN F[n]
+
<p> 有时算法的运行时间,不仅与问题规模有关,还与初始数据相关。这种情况下,需要分析算法的最好情况、最坏情况、平均情况的时间复杂度。
 
+
</p><p> 以插入排序为例分析。
 
+
</p><p> 设初始数据<span style="font-size:large;">a</span><span style="font-size:medium;"><sub>1</sub></span><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>n</sub></span>,插入排序的实现思想是:
 
+
</p>
== 递归算法的时间复杂度分析 ==
+
<ol><li> 初始<span style="font-size:large;">a</span><span style="font-size:medium;"><sub>1</sub></span>已排好序;
 
+
</li>
递归算法和分治算法中,都用到了递归思想。大问题的求解依赖于子问题的求解,因此它们的时间复杂度T(n)可用自身表示,即得到关于T(n)的递归方程。
+
<li> 若前面i-1个元素已排序,<span style="font-size:large;">a</span><sub>i</sub>依次与<span style="font-size:large;">a</span><sub>i-1,</sub><span style="font-size:large;">a</span><sub>i-2,…</sub><span style="font-size:large;">a</span><sub>1</sub>比较,插入适当位置,完成<span style="font-size:large;">a</span><sub>i</sub>的排序,i=2,3,…n。
 
+
</li></ol><p> 假设对数据10 40 30 5降序排序,插入排序的计算过程为:
=== 分析Fibonacci序列递归算法的时间复杂度。 ===
+
</p><p> 初始:只有10排好序。
 
+
</p><p> 第一趟:将40插入到10中,大于10,插入10之前,已排序元素为:
根据算法3.5可知,该算法的伪代码描述为:
+
</p><p>&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160; &#160;&#160;&#160;&#160;&#160;&#160; 40 &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160;10
 
+
</p><p>第 二趟:将30插入到40 10中,30大于10、小于40,插入40之后,已排序元素为:
Fib(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;
+
</p><p>&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160; &#160;&#160;&#160;&#160;&#160;&#160; 40&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160; 30 &#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160; 10
 
+
</p><p> 第三趟:将5插入到40 30 10中,小于10,插入10之后,已排序元素为:
1&nbsp; IF n≤2
+
</p><p>&#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; 40 &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160;30 &#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160; 10 &#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160;&#160; 5
 
+
</p><p> 最好情况分析:最好情况是初始数据已按序排列。这种情况下,插入<span style="font-size:large;">a</span><sub>i</sub><b> </b> 只需与<b><!--[if gte vml 1]><v:shapetype
2 &nbsp; &nbsp;THEN RETURN 1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 
 
 
3&nbsp; RETURN Fib(n-1)+Fib(n-2)&nbsp;&nbsp;
 
 
 
设递归计算第n项的运行时间为T(n)。根据算法描述,当n≤2时,T(n)的计算时间是常数值,T(1)=T(2)=1;当n>2时,计算F<sub>n</sub>,需先计算F<sub>n-1</sub>、F<sub>n-2</sub>,再加判定等其它操作,得到T(n)=T(n-1)+T(n-2)+2。
 
 
 
因此,T(n)的递归方程为:
 
 
 
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span style="font-size:large;">T</span>(n)=1 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;<span style="font-size:large;">n≤2</span>
 
 
 
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span style="font-size:large;">T</span>(n)=<span style="font-size:large;">T</span>(n-1)+<span style="font-size:large;">T(</span>n-2)+2 &nbsp; <span style="font-size:large;">n>2</span>
 
 
 
&nbsp;&nbsp;&nbsp; 显然,T(n)≥F<sub>n</sub>,而F<sub>n</sub>的通项公式是:
 
 
 
&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[[File:9.3.2.png|RTENOTITLE]]
 
 
 
故Fibonacci序列递归算法的时间复杂度下界是:
 
 
 
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;[[File:9.3.3.png|RTENOTITLE]]
 
 
 
是指数时间复杂度。 &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;
 
 
 
从时间复杂度来讲,Fibonacci数列的动态规划算法优于递归算法。
 
 
 
== 最好、最坏、平均情况时间复杂度分析 ==
 
 
 
有时算法的运行时间,不仅与问题规模有关,还与初始数据相关。这种情况下,需要分析算法的最好情况、最坏情况、平均情况的时间复杂度。
 
 
 
以插入排序为例分析。
 
 
 
设初始数据<span style="font-size:large;">a</span><span style="font-size:medium;"><sub>1</sub></span><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>n</sub></span>,插入排序的实现思想是:
 
 
 
# 初始<span style="font-size:large;">a</span><span style="font-size:medium;"><sub>1</sub></span>已排好序;
 
# 若前面i-1个元素已排序,<span style="font-size:large;">a</span><sub>i</sub>依次与<span style="font-size:large;">a</span><sub>i-1,</sub><span style="font-size:large;">a</span><sub>i-2,…</sub><span style="font-size:large;">a</span><sub>1</sub>比较,插入适当位置,完成<span style="font-size:large;">a</span><sub>i</sub>的排序,i=2,3,…n。
 
 
 
假设对数据10 40 30 5降序排序,插入排序的计算过程为:
 
 
 
初始:只有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;10
 
 
 
二趟:将30插入到40 10中,30大于10、小于40,插入40之后,已排序元素为:
 
 
 
&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;&nbsp;&nbsp; 30 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 10
 
 
 
第三趟:将5插入到40 30 10中,小于10,插入10之后,已排序元素为:
 
 
 
&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
 
 
  id="_x0000_t75" coordsize="21600,21600" o:spt="75" o:preferrelative="t"
 
  id="_x0000_t75" coordsize="21600,21600" o:spt="75" o:preferrelative="t"
 
  path="m@4@5l@4@11@9@11@9@5xe" filled="f" stroked="f">
 
  path="m@4@5l@4@11@9@11@9@5xe" filled="f" stroked="f">
第153行: 第101行:
 
  <v:imagedata src="file:///C:\Users\lad\AppData\Local\Temp\msohtmlclip1\01\clip_image001.wmz"
 
  <v:imagedata src="file:///C:\Users\lad\AppData\Local\Temp\msohtmlclip1\01\clip_image001.wmz"
 
   o:title=""/>
 
   o:title=""/>
</v:shape><![endif]-->''' ​<span style="font-size:large;">a</span><sub>i-1</sub>比较,插入'''<!--[if gte vml 1]><v:shape
+
</v:shape><![endif]--></b> ​<span style="font-size:large;">a</span><sub>i-1</sub>比较,插入<b><!--[if gte vml 1]><v:shape
 
  id="_x0000_i1026" type="#_x0000_t75" style='width:18.75pt;height:18pt;
 
  id="_x0000_i1026" type="#_x0000_t75" style='width:18.75pt;height:18pt;
 
  mso-position-horizontal-relative:page;mso-position-vertical-relative:page'
 
  mso-position-horizontal-relative:page;mso-position-vertical-relative:page'
第159行: 第107行:
 
  <v:imagedata src="file:///C:\Users\lad\AppData\Local\Temp\msohtmlclip1\01\clip_image001.wmz"
 
  <v:imagedata src="file:///C:\Users\lad\AppData\Local\Temp\msohtmlclip1\01\clip_image001.wmz"
 
   o:title=""/>
 
   o:title=""/>
</v:shape><![endif]-->'''<sub><span style="font-size:large;">a</span><sub>i-1</sub></sub>之后。之后。分析时间复杂度,循环插入数据n-1个,每插入一个数据,只需比较1次,因此插入排序最好情况的时间复杂度为O(n)。&nbsp;
+
</v:shape><![endif]--></b><sub><span style="font-size:large;">a</span><sub>i-1</sub></sub>之后。之后。分析时间复杂度,循环插入数据n-1个,每插入一个数据,只需比较1次,因此插入排序最好情况的时间复杂度为O(n)。&#160;
 
+
</p><p> 最坏情况分析:最坏情况是初始数据完全逆序排列。这种情况下,插入<span style="font-size:large;">a</span><sub>i</sub><b> </b> 需依次与<span style="font-size:large;">a</span><sub>i-1,</sub><span style="font-size:large;">a</span><sub>i-2,…,</sub><span style="font-size:large;">a</span><sub>1</sub><span style="font-size:large;">a</span><span style="font-size: 12px; line-height: 17.3333px;">1</span>之前。分析时间复杂度,循环插入数据n-1个,插入<span style="font-size:large;">a</span><sub>i</sub>(i=2,…,n),需循环比较i-1次。因此,插入排序最坏情况的总循环次数为1+2+…+n-1,时间复杂度为<span style="font-size:medium;">O(n<sup>2</sup>)</span>。
最坏情况分析:最坏情况是初始数据完全逆序排列。这种情况下,插入<span style="font-size:large;">a</span><sub>i</sub>''' ''' 需依次与<span style="font-size:large;">a</span><sub>i-1,</sub><span style="font-size:large;">a</span><sub>i-2,…,</sub><span style="font-size:large;">a</span><sub>1</sub><span style="font-size:large;">a</span><span style="font-size: 12px; line-height: 17.3333px;">1</span>之前。分析时间复杂度,循环插入数据n-1个,插入<span style="font-size:large;">a</span><sub>i</sub>(i=2,…,n),需循环比较i-1次。因此,插入排序最坏情况的总循环次数为1+2+…+n-1,时间复杂度为<span style="font-size:medium;">O(n<sup>2</sup>)</span>。
+
</p><p> 平均情况分析:算法的平均情况时间分析是取所有可能输入的平均运行时间。此时,需要考虑所有输入的概率问题。
 
+
</p><p> 假设前i-1个元素已排序好,<span style="font-size:large;">a</span>i有i个插入位置,如图1所示。<span style="line-height: 1.6;">&#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160;</span>
平均情况分析:算法的平均情况时间分析是取所有可能输入的平均运行时间。此时,需要考虑所有输入的概率问题。
+
</p><p>&#160; &#160; &#160; &#160; &#160; &#160;&#160;<img src="/nhpccwiki/images/e/ed/9.3.4.png" _fck_mw_filename="9.3.4.png" _fck_mw_origimgwidth="437" _fck_mw_origimgheight="62" alt="RTENOTITLE" title="RTENOTITLE" style="vertical-align:middle;" />
 
+
</p><p>&#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160;<span style="font-size:medium;">&#160;图1 ai的插入位置图</span>
假设前i-1个元素已排序好,<span style="font-size:large;">a</span>i有i个插入位置,如图1所示。<span style="line-height: 1.6;">&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;</span>
+
</p><p> 每个位置插入概率相等,为1/i。插入第1个位置需循环比较i-1次,插入第j(2≤j≤i)个位置需循环比较i-j+1次。故插入<span style="font-size:large;">a</span>i的平均循环次数Ti为:
 
+
</p><p>&#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; <img src="/nhpccwiki/images/d/d6/9.3.5.png" _fck_mw_filename="9.3.5.png" _fck_mw_origimgwidth="204" _fck_mw_origimgheight="49" alt="RTENOTITLE" title="RTENOTITLE" style="vertical-align:middle;" />&#160; &#160; &#160; &#160; &#160;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;[[File:9.3.4.png|RTENOTITLE]]
+
</p><p> 分别将<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)为:
 
+
</p><p>&#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160;<img src="/nhpccwiki/images/1/10/9.3.6.png" _fck_mw_filename="9.3.6.png" _fck_mw_origimgwidth="293" _fck_mw_origimgheight="46" alt="RTENOTITLE" title="RTENOTITLE" style="vertical-align:middle;" />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span style="font-size:medium;">&nbsp;图1 ai的插入位置图</span>
+
</p><p>因为: &#160; &#160; &#160; &#160; &#160; &#160; &#160;  
 
+
</p><p>&#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160;<img src="/nhpccwiki/images/4/46/9.3.7.png" _fck_mw_filename="9.3.7.png" _fck_mw_origimgwidth="114" _fck_mw_origimgheight="46" alt="RTENOTITLE" title="RTENOTITLE" style="vertical-align:middle;" />
每个位置插入概率相等,为1/i。插入第1个位置需循环比较i-1次,插入第j(2≤j≤i)个位置需循环比较i-j+1次。故插入<span style="font-size:large;">a</span>i的平均循环次数Ti为:
+
</p><p> 所以: &#160; &#160; &#160; &#160; &#160; &#160; &#160;
 
+
</p><p>&#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160;<img src="/nhpccwiki/images/e/ea/9.3.8.png" _fck_mw_filename="9.3.8.png" _fck_mw_origimgwidth="146" _fck_mw_origimgheight="40" alt="RTENOTITLE" title="RTENOTITLE" style="vertical-align:middle;" />
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [[File:9.3.5.png|RTENOTITLE]]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;
+
</p><p>得到插入排 序平均情况下的时间复杂性是<span style="font-size:large;">O(n<sup>2</sup>)</span>
 
+
</p><p> 因插入排序的运行时间介于最好情况与最坏情况之间,用界符号表示有:插入排序的时间复杂度上界为<span style="font-size:large;">O(n<sup>2</sup>)</span>(最坏情况),时间复杂度下界为Ω(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)为:
+
</p>
 
 
&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; &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>(最坏情况),时间复杂度下界为Ω(n)(最好情况)。两者不同阶,不能用准确界表示插入排序的时间复杂度。
 

2015年10月24日 (六) 12:59的版本

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

概念

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

                              <img src="/nhpccwiki/images/d/d5/9.3.1.png" _fck_mw_filename="9.3.1.png" _fck_mw_origimgwidth="118" _fck_mw_origimgheight="43" alt="RTENOTITLE" title="RTENOTITLE" style="vertical-align:middle;" />

就称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的通项公式是:

                            <img src="/nhpccwiki/images/b/bc/9.3.2.png" _fck_mw_filename="9.3.2.png" _fck_mw_origimgwidth="196" _fck_mw_origimgheight="48" alt="RTENOTITLE" title="RTENOTITLE" style="vertical-align:middle;" />

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

                           <img src="/nhpccwiki/images/9/94/9.3.3.png" _fck_mw_filename="9.3.3.png" _fck_mw_origimgwidth="194" _fck_mw_origimgheight="58" alt="RTENOTITLE" title="RTENOTITLE" style="vertical-align:middle;" />

是指数时间复杂度。                                                            

从时间复杂度来讲,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所示。                                                                                                 

            <img src="/nhpccwiki/images/e/ed/9.3.4.png" _fck_mw_filename="9.3.4.png" _fck_mw_origimgwidth="437" _fck_mw_origimgheight="62" alt="RTENOTITLE" title="RTENOTITLE" style="vertical-align:middle;" />

                        图1 ai的插入位置图

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

                <img src="/nhpccwiki/images/d/d6/9.3.5.png" _fck_mw_filename="9.3.5.png" _fck_mw_origimgwidth="204" _fck_mw_origimgheight="49" alt="RTENOTITLE" title="RTENOTITLE" style="vertical-align:middle;" />         

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

               <img src="/nhpccwiki/images/1/10/9.3.6.png" _fck_mw_filename="9.3.6.png" _fck_mw_origimgwidth="293" _fck_mw_origimgheight="46" alt="RTENOTITLE" title="RTENOTITLE" style="vertical-align:middle;" />

因为:              

                 <img src="/nhpccwiki/images/4/46/9.3.7.png" _fck_mw_filename="9.3.7.png" _fck_mw_origimgwidth="114" _fck_mw_origimgheight="46" alt="RTENOTITLE" title="RTENOTITLE" style="vertical-align:middle;" />

所以:              

                 <img src="/nhpccwiki/images/e/ea/9.3.8.png" _fck_mw_filename="9.3.8.png" _fck_mw_origimgwidth="146" _fck_mw_origimgheight="40" alt="RTENOTITLE" title="RTENOTITLE" style="vertical-align:middle;" />

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

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