前面刚刚阐明，对于时间复杂度分别为n和n²的两种算法，无论两种算法需要多长时间来处理基本运算，当n值足够大时，第一种算法的效率总是高于第二种。现在假定同一问题有两种算法，而且第一种算法的所有情况时间复杂度为100n，第二种算法为0.01n²。根据上面刚刚给出的论述，可以证明，第一种算法的效率最终会高于第二种算法。例如，如果两种算法处理基本运算需要的时间相同，而且开销时间也大致相同，则当 0.01n² > 100n 时，第一种算法更为高效。 两边同除以0.01n，得： n > 10 000 如果第一种算法处理基本运算的时间长于第二种算法，第一种算法最终还是会变得更为高效，只是n值要更大一些。 时间复杂度为n和100n的算法称为线性时间算法（linear-time algorithm），因为它们的时间复杂度是输入规模n的线性函数，而时间复杂度为n²和0.01n²的算法称为二次时间算法（quadratic-time algorithm），因为它们的时间复杂度是输入规模n的二次函数。这里有一条基本原理，即，任意线性时间算法的效率最终将高于任意二次时间算法。在算法的理论分析中，我们关心的是最终行为。下面将说明如何根据算法的最终行为对其进行分组。这样就可以轻松地判断一组算法的最终行为是否高于另一组算法。 1.4.1 阶的直观介绍 诸如5n²和5n²+100的函数称为纯二次函数（pure quadratic function），因为它们没有包含线性项，而诸如0.1n²+n+100之类的函数则称为完全二次函数（complete quadratic function），因为它们包含有线性项。表1-3表明，二次项最终在函数中占据主导地位。也就是说，与这个二次项的取值相比，其他项目的取值最终将变得微不足道。因此，尽管这个函数不是纯二次函数，但可以将它划分为纯二次函数一类。这就是说，某个算法具有这种时间复杂度，就可以将其称为二次时间算法。从直观上来说，在为复杂度函数分类时，应当总可以扔掉低阶项。例如，似乎应当可以将0.1n³+10n²+5n+25划分为纯三次函数。后面马上就会严格证明是可以这样做的。首先让我们直观感受一下，看看如何划分复杂度函数。 所有可以划分为纯二次函数的复杂度函数构成一个集合，称为Θ(n²)，其中Θ是大写希腊字母“西塔”。如果一个函数是集合Θ(n²)的元素，就说该函数为n²阶。例如，由于可以抛弃低阶项，所以 这意味着g(n)是n²阶的。作为一个更具体的例子，回想1.3.1节中，算法1.3（交换排序）的时间复杂度由T(n)=n(n-1)/2给出。因为 抛弃低阶项n/2，可证明T(n) Θ(n²)。 当一个算法的时间复杂度属于Θ(n²)时，将该算法称为二次时间算法或Θ(n²)算法，也称该算法是Θ(n²)的。交换排序是一种二次时间算法。 与此类似，可以用纯三次函数归类的复杂度函数集合称为Θ(n³)，并称这个集合中的函数是n³阶的，以此类推。我们将这些集合称为复杂度类别（complexity category）。下面是一些最常见的复杂度类别： 根据这一排序，如果f(n)所在类别位于g(n)所属类别的左侧，则f(n)的曲线最终将低于g(n)。图1-3画出了这些类别中一些最简单成员的曲线：n，lnn，nlnn，等等。表1-4给出了一些算法的执行时间，这些算法的时间复杂度由上述函数给出。这里做了一个简化假设：处理每种算法的基本运算需要1 纳秒（![enter image description here][5]秒）。表中结果可能会让人感到惊讶。有人可能会想，只要一条算法不是指数时间算法，那应当就够了。但是，即使是二次时间算法，也需要31.7年的时间来处理一个输入规模为10亿的实例。而Θ(nlnn)算法处理这样一个实例只需要29.9秒。一般情况下，一个算法必须是Θ(nlnn)或更佳时，我们才能假定它可以在可容忍时间内处理极大实例。这并不是说，如果时间复杂度属于更高阶类别，那这种算法就没有用了。具有二次、三次甚至更高阶时间复杂度的算法，经常可以处理在许多应用中出现的实例。 在结束这一讨论之前要强调一点：与仅知道阶数相比，准确地知道时间复杂度可以掌握更多信息。例如，回想一下前面讨论的假想算法，它们的时间复杂度为100n和0.01n²。如果需要相同的时间来处理两种算法的基本运算，执行其开销指令，那当实例小于10 000时，二次时间算法的效率要更高一些。如果应用中从来不需要超过此数值的实例，那就应当实现二次时间算法。如果只知道时间复杂度分别属于Θ(n)和Θ(n²)，那就无法掌握以上信息。这个例子中的系数属于极端情况，在实践中，它们通常不会这样极端。此外，有时很难准确得出时间复杂度。因此，有时会满足于仅求出阶数。 1.4.2 阶数的严谨介绍 前面的讨论让我们对阶（Θ）有了直观的感受。下面将发展一种可以准确定义阶的理论。为此，给出另外两个基础概念。第一个是“大O”。 定义 对于给定复杂度函数f(n)，O(f(n))是由一些复杂度函数g(n)组成的集合，对于其中每个g(n)，必存在某一正实常数c及某一非负整数N，使得对于所有n≥N，满足 g(n)≤c×f(n) 如果g(n) O(f(n))，就说g(n)是f(n)的大O。图1-4a显示了“大O”。尽管在该图中，g(n)的起始位置高于cf(n)，但最终落在cf(n)之下，并保持这种状态。图1-5给出了一个具体例子。尽管n²+10n在图中的起始位置高于2n²，但对于n≥10，则有 n²+10n≤2n² 因此可以在“大O”的定义中取c=2和N=10，得出结论： n²+10n∈O(n²) 例如，如果g(n)属于O(n²)，g(n)的曲线最终将位于某个纯二次函数cn²之下。这就意味着，如果g(n)是某一算法的时间复杂度，那该算法的运算时间最终将至少与二次函数一样快。从分析的角度来说，可以说g(n)最终将会与纯二次函数一样好。我们说“大O”（以及马上将会介绍的其他概念）描述了一个函数的渐近（asymptotic）特性，这是因为它们只与最终特性有关。我们说“大O”设定了一个函数的渐近上限（asymptotic upper bound）。 下面的例子说明如何证明“大O”。 例1.7 证明5n²∈ O(n²)。因为对于n≥0，有 5n²≤5n² 所以取c=5，N=0，即可得到所需要的结果。 例1.8 回想一下，算法1.3（交换排序）的时间复杂度由下式给出： 所以取c=1/2，N=0，可以得出结论T(n) ∈O(n²)。 学生们在学习“大O”时的难点在于，他们经常错误地认为必须要找到一个唯一的c和唯一的N，才能证明一个函数是另一个函数的“大O”。事实并非如此。回想一下，图1-5使用c=2和N=10证明了n²+10n∈ O(n²)。或者，也可以像下面这样证明。 例1.9 证明n²+10n∈O(n²)。因为对于n≥1，有 n²+10n≤n²+10n²=11n² 所以取c=11，N=1，可以得到想要的结果。 一般情况下，可以使用看起来最直接的操作来证明“大O”。 例1.10 证明n²∈O(n²+10n)。因为对于n≥0，有 n²≤1×(n²+10n) 所以取c=1，N=0，可以得到想要的结果。 这个例子是希望表明：“大O”中的函数不一定必须是图1-3中绘制的简单函数。它可以是任意复杂度函数。但一般情况下，我们会取类似于图1-3中绘制的简单函数。 例1.11 证明n O(n²)。因为对于n≥1，有 n≤1×n² 所以取c=1，N=1，可以得到想要的结果。 最后这个例子阐明了有关“大O”的一个重要论述。O(n²)中的复杂度函数并非一定要有二次项。只要它的曲线最终低于某个纯二次函数即可。因此，任何对数或线性复杂度函数都属于O(n²)。同样，任何对数、线性或二次复杂度函数都属于O(n³)，以此类推。图1-6a给出了O(n²)的一些代表性元素。 “大O”为复杂度设定了渐近上限，而下面的概念则为复杂度函数设定了渐近下限（asymptotic lower bound）。 定义 对于给定复杂度函数f(n)，Ω(f(n))是由一些复杂度函数g(n)组成的集合，对于其中每个g(n)，必存在某一正实常数c及某一非负整数N，使得对于所有n≥N，满足 g(n)≥c×f(n) 符号Ω是大字希腊字母“欧米伽”。如果g(n) Ω(f(n))，就说g(n)是f(n)的欧米伽。图1-4b演示了Ω。下面给出一些例子。 例1.12 证明5n²∈Ω(n²)。因为对于n≥0，有 5n²≥1×n² 所以取c=1，N=0，可以得到想要的结果。 例1.13 证明n²+10n∈Ω(n²)。因为对于所有n≥0，有 n²+10n≥n² 所以取c=1，N=0，可以得到想要的结果。 例1.14 再次考虑算法1.3（交换排序）的时间复杂度。证明： 这就意味着，取c=1/4，N=2，可以得到想要的结果。 和“大O”中的情景一样，满足Ω定义条件的常数c和N并不唯一。可以选择使操作最容易的一对。 如果一个函数属于Ω(n²)，该函数的曲线最终将位于某一纯二次函数之上。对分析来说，这意味着它最终至少会像一个纯二次函数一样差。但是，如下例所示，这个函数不一定是二次函数。 例1.15 证明n³∈Ω(n²)。因为对于n≥1，有 n³≥1×n² 所以取c=1，N=1，可以得到想要的结果。 图1-6b给出了Ω(n²)的一些代表性元素。 如果一个函数同时属于O(n2)和Ω(n2)，可以得出结论：这个函数的曲线最终将位于某一纯二次函数之下，且又最终位于某一纯二次函数之上。也就是说，它最终至少会像某个纯二次函数一样好，且又最终至少会像某个纯二次函数一样差。因此可以得出结论，它的增长速度类似于一个纯二次函数。这正是我们所想要的阶的严格概念的结果。有以下定义。 定义 对于一个给定的复杂度函数f(n)，![enter image description here][5]这意味着Θ(f(n))是由一些复杂度函数g(n)组成的集合，对于其中每个g(n)，必存在某正实常数c和d，及某一非负整数N，使得对于所有n≥N，满足 c×f(n)≤g(n)≤d×f(n) 若g(n)∈ Θ(f(n))，就说g(n)是f(n)的阶（order）。 例1.16 再次考虑算法1.3的时间复杂度。例1.8和例1.14一同证明了 这意味着T(n)∈ O(n²)∩Ω(n²)=Θ(n²)。 图1-6c显示Θ(n²)是O(n²)和Ω(n²)的交集，而图1-4c则显示了Θ。在图1-6c中注意5n+7不属于Ω(n²)，函数4n³+3n²不属于O(n²)。因此，这两个函数都不属于Θ(n²)。尽管这在直觉上是正确的，但我们还没有证明它。下面的例子说明如何进行此种证明。 例1.17 用反证法（矛盾法）证明n不属于Ω(n²)。在这种证明方法中，假设某一论述为正确，在本例中假设n Ω(n²)，然后进行推导，得出一个不正确的结果。也就是说，此结果与某个已知正确的论述矛盾。于是，可以得出结论，前面做出的假设不可能是正确的。 假设n Ω(n²)，也就是假设存在某个正常数c和某个非负整数N，使得对于n≥N，有 n≥cn² 如果在此不等式两边除以cn，则对于n≥N，有 但是，对于任意n>1/c，此不等式都不成立，这就意味着，它不可能对于所有n≥N都成立。这一矛盾证明了n不属于Ω(n²)。 还有另外一个有关“阶”的定义，它表达了诸如函数n与函数n²之间的关系。 定义 对于一个给定的复杂度函数f(n)，o(f(n))是由所有满足以下条件的复杂度函数g(n)组成的集合：对于每个正实常数c，必存在一个非负整数N，使得对于所有n≥N，有 g(n)≤c×f(n) 如果g(n) ∈o(f(n))，就说g(n)是f(n)的小o。回忆一下，“大O”是指必然存在某个正实常数c，使此上限成立。这一定义是说，该上限必须对于每个正实常数c成立。因为此上限对于每个正数c成立，所以它对任意小的c也成立。例如，如果g(n) o(f(n))，则存在一个N，使得当n>N时， g(n)≤0.000 01×f(n) 可以看到，当n变得很大时，g(n)相对于f(n)来说变得微不足道。对于分析来说，如果g(n)属于o(f(n))，则g(n)最终将远优于诸如f(n)之类的函数。下面的例子说明了这一点。 例1.18 证明 n∈ o(n²) 给定c>0。需要找出一个N，使得对于n≥N，满足 n≤cn² 如果将此不等式的两边同除以cn，得： 因此，选择任意N≥1/c就足够了。 注意，N的值取决于常数c。例如，若c = 0.000 01，必须使N最小为100 000。也就是说，对于n≥100 000，有 n≤0.000 01n² 例1.19 证明n不属于o(5n)。下面将使用反证法进行证明。令。若n∈ o(5n)，则必然存在某个N值，使得对于n≥N， 这一矛盾证明了n不属于o(5n)。 下面的定理给出了“小o”与其他渐近符号之间的关系。 定理1.2 若g(n)∈ o(f(n))，则 g(n)∈ O(f(n))-Ω(f(n)) 即，g(n)属于O(f(n))，但不属于Ω(f(n))。 证明：因为g(n) ∈o(f(n))，所以对于每个正实常数c，必存在一个N，使得对于所有n≥N，有 g(n)≤c×f(n) 这意味着该上限当然对某个c值成立。因此， g(n) ∈O(f(n)) 我们将使用反证法证明g(n)不属于Ω(f(n))。如果g(n) Ω(f(n))，则存在某一实常数c>0和某个，使得对于所有n≥，有 g(n)≥c×f(n) 但因为g(n) ∈o(f(n))，所以存在某个，使得对于所有n≥，有 但这些不等式必须对于所有大于和的n值都成立。这一矛盾证明了g(n)不可能属于Ω(f(n))。 你可能会想o(f(n))和O(f(n))-Ω(f(n))必然是同一集合。并非如此。有一些不常见的函数，属于O(f(n))-Ω(f(n))，但不属于o(f(n))。下例证实了这一点。 例1.20 考虑下面的函数： 将以下证明留作练习： g(n)∈ O(n)-Ω(n)，但g(n)不属于o(n)。 当然，例1.20是故意设计的。当复杂度函数表示实际算法的时间复杂度时，O(f(n))-Ω(f(n))中的函数通常就是o(f(n))中的函数。 现在深入讨论Θ。在习题中我们证明了： g(n) ∈Θ(f(n))等价于f(n) ∈Θ(g(n)) 例如， n²+10n ∈Θ(n²)，n² ∈Θ(n²+10n) 这意味着Θ将复杂度函数划分到不交集中。我们将这些集合称为复杂度类别。给定类别中的任何一个函数都可以表示该类别。为方便起见，通常用一个类别中最简单的元素来代表该类别。上一个示例类别由Θ(n²)表示。 某些算法的时间复杂度不随n递增。例如，回想一下，算法1.1的最佳情况时间复杂度B(n)对于所有n值都为1。包含此类函数的复杂度类别可以用任意常数表示，为简便起见，我们用Θ(1)表示它。 下面给出“阶”的一些重要性质，利用这些性质，可以轻松地确定许多复杂度函数的阶。这些性质直接给出，未加证明。一些证明会在习题中推导，而另外一些证明则可以由下一小节获得的结果推导得出。第二个结果已在前面讨论过。将它包含在这里只是出于完整性考虑。 阶的性质 (1) g(n) ∈O(f(n))，当且仅当 f(n)∈ Ω(g(n))。 (2) g(n)∈ Θ(f(n))，当且仅当f(n) ∈Θ(g(n))。 (3) 若b>1，a>1，则。 这意味着所有对数复杂度函数都属于同一复杂度类别，我们用Θ(lgn)代表这一类别。 (4) 若b>a>0，则 。 这意味着所有指数复杂度函数都不在同一复杂度类别中。 (5) 对于所有a>0，有 。 这意味着n!比任何指数复杂度函数都要差。 (6) 思考复杂度类别的以下顺序： 其中k > j > 2，b > a > 1。若复杂度函数g(n)所在类别位于f(n)所在类别的左侧，则 g(n)∈ o(f(n)) (7) 若c≥0，d>0，g(n) ∈O(f(n))，且h(n)∈ Θ(f(n))，则 c×g(n)+d×h(n) ∈Θ(f(n)) 例1.21 性质3表明：所有对数复杂度函数都属于同一复杂度类别。例如， 这意味着、lgn之间的关系与7n²+5n、n²之间的关系相同。 例1.22 性质6表明：任意对数函数最终将优于任意多项式函数，任意多项式函数最终将优于任意指数函数，任意指数函数最终将优于阶乘函数。例如， 例1.23 性质6和性质7可重复使用。例如，可以证明5n+3lgn+10nlgn+7n²∈Θ(n²)，如下所示。重复应用性质6和性质7，有 在实践中，我们不会重复求助于这些性质，而是轻松地意识到可以抛弃低阶项。 如果可以得到一个算法的准确时间复杂度，只需抛弃低阶项目就能确定它的阶。如果无法获得这一信息，可以回过头来，借助于“大O”和Ω的定义来确定阶。例如，假定对于某些算法，无法准确求出T(n)[或W(n)，A(n)，B(n)]。如果能够直接利用定义证明： T(n) ∈O(f(n))及T(n) ∈Ω(f(n)) 就可以得出结论，T(n)∈ Θ(f(n))。 有时，很容易证明T(n) ∈O(f(n))，但难以确定T(n)是否属于Ω(f(n))。在这种情况下，我们可以满足于仅证明T(n) ∈O(f(n))，因为这意味着T(n)至少像f(n)这样的函数一样好。类似地，我们可以满足于仅知道T(n) ∈Ω(f(n))，因为这意味着T(n)至少像f(n)这样的函数一样差。 在结束讨论之前需要提一下，许多作者会说 f(n)=Θ(n²)，而不说f(n)∈ Θ(n²) 它们的意思实际是一样的，也就是说，f(n)是集合Θ(n²)的一个元素。同样，人们经常会写为 f(n)=O(n²)，而不是f(n)∈ O(n²) 关于“阶”的历史介绍，请参阅Knuth（1973年）的文献；关于本书对阶定义的讨论，请参阅Brassard（1985年）的文献。我们关于“大O”、Ω和Θ的定义大多数是标准的，但“小o”还有其他不同的定义方法。将Θ(n)、Θ(n²)等集合称为“复杂度类别”并不是标准做法。有些作者将它们称为“复杂度类”，尽管这一术语经常用来表示第9章讨论的问题集。而另外一些作者根本就没有为它们指定任何具体的名字。