查看“算法分析”的源代码

在[[计算机科学]]中，'''算法分析'''（{{lang-en|Analysis of algorithm}}）是分析执行一个给定[[算法]]需要消耗的[[计算资源]]数量（例如计算时间，存储器使用等）的过程。算法的效率或复杂度在理论上表示为一个[[函数]]。其定义域是输入数据的长度（通常考虑任意大的输入，没有上界），值域通常是执行步骤数量（[[时间复杂度]]）或者存储器位置数量（空间复杂度）。算法分析是[[计算复杂度理论]]的重要组成部分。

理论分析常常利用[[渐近分析]]估计一个算法的复杂度，并使用[[大O符号]]、[[大Ω符号]]和[[大Θ符号]]作为标记。举例，[[二分查找]]所需的执行步骤数量与查找列表的长度之对数成正比，记为 <math>O(\log n)</math>，简称为「对数时间」。通常使用[[渐近分析]]的原因是，同一算法的不同具体[[实现]]的效率可能有差别。但是，对于任何给定的算法，所有符合其设计者意图的实现，它们之间的性能差异应当仅仅是一个系数。

精确分析算法的效率有时也是可行的，但这样的分析通常需要一些与具体实现相关的假设，称为[[计算模型]]。计算模型可以用[[抽象机器]]来定义，比如[[图灵机]]。或者可以假设某些基本操作在单位时间内可完成。

假设二分查找的目标列表总共有 n 个元素。如果我们假设单次查找可以在一个时间单位内完成，那么至多只需要 <math>\log n + 1</math> 单位的时间就可以得到结果。这样的分析在有些场合非常重要。

算法分析在实际工作中是非常重要的，因为使用低效率的算法会显著降低系统性能。在对运行时间要求极高的场合，耗时太长的算法得到的结果可能是过期或者无用的。低效率算法也会大量消耗计算资源。

== 时间资源消耗 ==

[[时间复杂度]]分析和如何定义「一步操作」有紧密联系。作为算法分析成立的一项基本要求，单步操作必须能够在确定的常量时间内完成。

实际情况很复杂。举例，有些分析方法假定两个数相加是单个步骤，但这假定可能不成立。若被分析的算法可以接受任意大的数，则无法保证相加操作能够在确定的时间内完成。

通常有两种定义消耗的方法：<ref name="AhoHopcroft1974">{{cite book|author1=Alfred V. Aho|author2=John E. Hopcroft|author3=Jeffrey D. Ullman|title=The design and analysis of computer algorithms|year=1974|publisher=Addison-Wesley Pub. Co.}}, section 1.3</ref>
<ref name="Hromkovič2004">{{cite book|author=Juraj Hromkovič|title=Theoretical computer science: introduction to Automata, computability, complexity, algorithmics, randomization, communication, and cryptography|url=http://books.google.com/books?id=KpNet-n262QC&pg=PA177|year=2004|publisher=Springer|isbn=978-3-540-14015-3|pages=177–178}}</ref>
<ref name="Ausiello1999">{{cite book|author=Giorgio Ausiello|title=Complexity and approximation: combinatorial optimization problems and their approximability properties|url=http://books.google.com/books?id=Yxxw90d9AuMC&pg=PA3|year=1999|publisher=Springer|isbn=978-3-540-65431-5|pages=3–8}}</ref>
<ref name=Wegener20>{{Citation|last1=Wegener|first1=Ingo|title=Complexity theory: exploring the limits of efficient algorithms|publisher=[[Springer-Verlag]]|location=Berlin, New York|isbn=978-3-540-21045-0|year=2005|page=20|url=http://books.google.com/books?id=u7DZSDSUYlQC&pg=PA20}}</ref>
<ref name="Tarjan1983">{{cite book|author=[[Robert Endre Tarjan]]|title=Data structures and network algorithms|url=http://books.google.com/books?id=JiC7mIqg-X4C&pg=PA3|year=1983|publisher=SIAM|isbn=978-0-89871-187-5|pages=3–7}}</ref>

* 单一消耗：每一步操作的消耗定义为一个常量，与参与运算的数据的大小无关。
* 对数消耗：每一步操作的消耗，均与参与运算的数据的长度（位数）成正比。

后者更难以应用，所以只在必要时使用。一个例子是对接受任意精度数据的算法（比如[[密码学]]中用到的一些算法）的分析。

人们常常忽略一点：算法的效率的理论界限，通常建立在比实际情况更加严格的假定之上。因此在实际中，算法效率是有可能突破理论的界限的。<ref>[http://cstheory.stackexchange.com/questions/608/examples-of-the-price-of-abstraction Examples of the price of abstraction?], cstheory.stackexchange.com</ref>

===经验分析的缺陷===

算法是[[平台无关]]的，也即一个算法可以在任意[[计算机]]、任意[[操作系统]]上、用任意[[编程语言]]实现。因此，算法性能的相对好坏，不能仅仅通过基于运行记录的经验来判断。

举例：一个程序在大小为 n 的有序数组中搜索元素。假设该程序在一台先进的电脑 A 上用[[线性搜索]]实现，在一台老旧的电脑 B 上用[[二分搜索]]实现。性能测试的结果可能会如下：
{| class="wikitable"
|-
! 数组长度 n
! 计算机 A 的运行时间<br />（以[[纳秒]]计）
! 计算机 B 的运行时间<br />（以[[纳秒]]计）
|-
| 15
| 7 
| 100,000 
|-
| 65
| 32 
| 150,000 
|-
| 250
| 125 
| 200,000 
|-
| 1,000
| 500 
| 250,000 
|}

通过这些数据，很容易得出结论说计算机 A 运行的算法比计算机 B 的算法要高效得多。但假如输入的数组长度显著增加的话，很容易发现这个结论的错误。
以下是另一组数据：

{| class="wikitable"
|-
! 数组长度 n 
! 计算机 A 的运行时间<br />（以[[纳秒]]计）
! 计算机 B 的运行时间<br />（以[[纳秒]]计）
|-
| 15
| 7 
| 100,000 
|-
| 65
| 32 
| 150,000 
|-
| 250
| 125 
| 200,000 
|-
| 1,000
| 500 
| 250,000 
|-
| ...
| ...
| ...
|-
| 1,000,000
| 500,000
| 500,000
|-
| 4,000,000
| 2,000,000
| 550,000
|-
| 16,000,000
| 8,000,000
| 600,000
|-
| ...
| ...
| ...
|-
| 63,072 &times; 10<sup>12</sup>
| 31,536 &times; 10<sup>12</sup>纳秒，<br />约等于 1 年
| 1,375,000 纳秒，<br />或 1.375 毫秒
|}

计算机 A 运行的线性搜索算法具有[[线性时间]]。它的运行时间直接与输入规模成正比。输入大小若加倍，运行时间同样加倍。而计算机 B 运行的二分搜索算法具有[[对数时间]]。输入大小若加倍，运行时间仅仅增加一个常量，在此例中是 25,000 纳秒。即使计算机 A 明显性能更强，在输入不断增加的情况下，计算机 B 的运行时间终究也会比计算机 A 更短，因为它运行的算法的增长率小得多。

===增长的阶===
{{main|大O符号}}

非正式地，如果一个关于 <math>n</math> 的函数 <math>f(n)</math>，乘以一个系数以后，能够为某个算法在输入数据大小 <math>n</math> 足够大的情况下的运行时间提供一个上界，那么称此算法按该函数的阶增长。一个等价的描述是，当输入大小 <math>n</math> 大于某个 <math>n_0</math> 时，存在某个常数 <math>c</math>，使得算法的运行时间总小于 <math>c\times f(n)</math>。常用[[大O符号]]对此进行描述。比如，[[插入排序]]的运行时间随数据大小二次增长，那么插入排序具有 <math>O(n^2)</math> 的时间复杂度。大O符号通常用于表示某个算法在最差情况下的运行时间，但也可以用来表述平均情况的运行时间。比如，[[快速排序]]的最坏运行时间是 <math>O(n^2)</math>，但是平均运行时间则是 <math>O(n \log n)</math>。<ref>在算法分析的场合里，常用 <math>\log</math> 或 <math>\lg</math> 作为 <math>\log_2</math> 的简称。</ref>

=== 运行时间复杂度的分析 ===

分析一个算法的最坏运行时间复杂度时，人们常常作出一些简化问题的假设，并分析该算法的结构。以下是一个例子：

 1    从输入值中获取一个正数
 2    '''if''' n > 10
 3        '''print''' "耗时可能较长，请稍候……"
 4    '''for''' i = 1 '''to''' n
 5        '''for''' j = 1 '''to''' i
 6            '''print''' i * j
 7    '''print''' "完成！"

一台给定的电脑执行每一条[[指令]]的时间是[[确定性模型|确定]]<ref>但这对[[量子计算机]]不成立。</ref>的，并可以用 [[DTIME]] 描述。
假设第 1 步操作需时 T<sub>1</sub>，第 2 步操作需时 T<sub>2</sub>，如此类推。

步骤 1、2、7 只会运行一次。应当假设在最坏情况下，步骤 3 也会运行。步骤 1 至 3 和步骤 7 的总运行时间是：

<math>T_1 + T_2 + T_3 + T_7</math>

步骤 4、5、6 中的[[循环]]更为复杂。步骤 4 中的最外层循环会执行 (n + 1) 次（需要一次执行来结束 for 循环，因此是 (n + 1) 次而非 n 次），因此会消耗 T<sub>4</sub> &times; (n + 1) 单位时间。内层循环则由 i 的值控制，它会从 1 [[迭代]]到 n。
第一次执行外层循环时，j 从 1 迭代到 1，因此内层循环也执行一次，总共耗时 T<sub>6</sub> 时间。以及内层循环的判断语句消耗 3T<sub>5</sub> 时间。

所以，内层循环的总共耗时可以用一个[[等差级数]]表示：

:<math>T_6 + 2T_6 + 3T_6 + \cdots + (n-1) T_6 + n T_6</math>

上式可被[[因式分解]]<ref>可用[[数学归纳法]]证明 <math>1 + 2 + 3 + \cdots + (n-1) + n = \frac{n(n+1)}{2}</math></ref>为：

:<math>T_6 \left[ 1 + 2 + 3 + \cdots + (n-1) + n \right] = T_6 \left[ \frac{1}{2} (n^2 + n) \right] </math>

类似地，可以分析内层循环的判断语句：

:<math>2T_5 + 3T_5 + 4T_5 + \cdots + (n-1) T_5 + n T_5 + (n + 1) T_5</math>

:<math> = T_5 + 2T_5 + 3T_5 + 4T_5 + \cdots + (n-1)T_5 + nT_5 + (n+1)T_5 - T_5</math>

上式可被分解为：

:<math>T_5 \left[ 1+2+3+\cdots + (n-1) + n + (n + 1) \right] - T_5 </math>

:<math> = \left[ \frac{1}{2} (n^2 + n) \right]  T_5 +  (n + 1)T_5 - T_5  </math>

:<math> =  T_5 \left[ \frac{1}{2} (n^2 + n) \right] + n T_5 </math>

:<math> =  \left[ \frac{1}{2} (n^2 + 3n) \right] T_5</math>

因此该算法的总运行时间为：

:<math>f(n) = T_1 + T_2 + T_3 + T_7 + (n + 1)T_4 + \left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2+3n) \right] T_5 </math>

改写一下：

:<math>f(n) = \left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7
</math>

通常情况下，一个函数的最高次项对它的增长率起到主导作用。在此例里，n² 是最高次项，所以有结论 <math>f(n) = O(n^2)</math>。

严格证明如下：证明 <math>\left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \le cn^2,\ n \ge n_0</math>

<math>\left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7</math>

<math>\le ( n^2 + n )T_6 + ( n^2 + 3n )T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \ (n \geq 0)</math> 

令 k 为一个常数，其大于从 T<sub>1</sub> 到 T<sub>7</sub> 所有的数。

<math>T_6( n^2 + n ) + T_5( n^2 + 3n ) + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \le k( n^2 + n ) + k( n^2 + 3n ) + kn + 5k</math>

<math>= 2kn^2 + 5kn + 5k \le 2kn^2 + 5kn^2 + 5kn^2 \, (n \geq 1) = 12kn^2</math>

因此有

<math>\left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \le cn^2, n \ge n_0</math>，其中 <math>c = 12k, n_0 = 1</math>

还可以假定所有步骤全部消耗相同的时间，它的值比 T<sub>1</sub> 到 T<sub>7</sub> 中任意一个都大。这样的话，这个算法的运行时间就可以这样来分析：<ref>比起上面的方法，这个方法忽略了结束循环的判断语句所消耗的时间，但很[[平凡 (数学)|明显]]可以证明这种忽略不影响最后结果。</ref>

<math>4+\sum_{i=1}^n i\leq 4+\sum_{i=1}^n n=4+n^2\leq5n^2 \, (n \geq 1) =O(n^2).</math>

==其他运算资源的增长率分析==

运用与分析时间相同的方法可以分析其他运算资源的消耗情况，比如存储器空间的消耗。例如，考虑以下一段管理一个文件的[[内存]]使用的[[伪代码]]：

 '''while''' (''文件打开'')
     '''令''' n = ''文件大小''
     '''for''' ''n 每增长 100kb''
         ''为该文件分配多一倍的内存空间''

在这个例子里，当文件大小 n 增长的时候，内存消耗会以指数增长，或 <math>O(2^n)</math>。这个速度非常快，很容易使得资源消耗失去控制。

==参见==
* [[平摊分析]]
* [[渐近分析]]
* [[渐近时间复杂度]]
* [[计算时间]]
* [[大O符号]]
* [[计算复杂性理论]]
* [[主定理]]
* [[NP-完全]]
* [[数值分析]]
* [[多项式时间]]
* [[程序优化]]
* [[性能分析]]
* [[可扩放性]]
* [[平滑分析]]
* [[时间复杂度]]，包括常见算法的增长率列表

==注释==
{{reflist}}

=== 来源 ===
{{refbegin}}
; 书籍
* {{cite book |authorlink=Thomas H. Cormen |first=Thomas H. |last=Cormen |authorlink2=Charles E. Leiserson |first2=Charles E. |last2=Leiserson |authorlink3=Ronald L. Rivest |first3=Ronald L. |last3=Rivest |lastauthoramp=yes |authorlink4=Clifford Stein |first4=Clifford |last4=Stein |title=[[Introduction to Algorithms]] |edition=Second |publisher=MIT Press and McGraw-Hill |location=Cambridge, MA |year=2001 |isbn=0-262-03293-7 |others=Chapter 1: Foundations |pages=3–122 }}
*{{Cite book |title=Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching |edition=3rd |authorlink=Robert Sedgewick (computer scientist) |first=Robert |last=Sedgewick |location=Reading, MA |publisher=Addison-Wesley Professional |year=1998 |isbn=978-0-201-31452-6 }}
*{{Cite book |title=[[The Art of Computer Programming]] |authorlink=Donald Knuth |first=Donald |last=Knuth |location= |publisher=Addison-Wesley |isbn= |year= }}
*{{Cite book |first=Daniel A. |last=Greene |first2=Donald E. |last2=Knuth |title=Mathematics for the Analysis of Algorithms |edition=Second |location= |publisher=Birkhäuser |year=1982 |isbn=3-7643-3102-X }}
*{{Cite book |authorlink=Oded Goldreich |first=Oded |last=Goldreich |title=Computational Complexity: A Conceptual Perspective |location= |publisher=[[Cambridge University Press]] |year=2010 |isbn=978-0-521-88473-0 }}
{{refend}}

{{-}}
{{Computer Science}}

{{DEFAULTSORT:Analysis Of Algorithms}}
[[Category:计算复杂性理论]]
[[Category:算法分析| ]]