下载掌阅APP，畅读海量书库
立即打开
让我们回顾一下LINEAR-SEARCH程序并计算它的运行时间。回顾第1章的知识可得，运行时间可以表示成一个关于输入规模的函数。这里，输入是一个包含 n 个元素的数组 A ，元素数目 n ，及要查找的值 x 。随着数组中元素规模的增加， n 本身的大小和 x 的值对运行时间影响不大——毕竟， n 仅仅是一个简单的整数且 x 仅仅可能与数组的 n 个元素中的某个元素值一样大——因此，这里所提到的输入规模 n 指的是数组 A 中元素的数目。
为了表示完成一项任务所花的时间，我们必须做一些简单的假设。我们将假定每步单独的操作——无论它是一个算术运算（例如加、减、乘、除）、比较、变量赋值、给数组标记索引操作，或者是程序调用、从程序中返回结果操作——均会花掉不依赖于输入规模的固定时间。
操作不同，各个操作所花费的时间可能也不同，例如除法操作可能比加法操作会花更长的时间。但是当一个步骤仅仅是由多个简单操作叠加而成时，该步骤会花费常量时间。由于各个步骤中所执行的操作所花费的时间不同，且根据第1章中所列举出的各种外在因素的影响可以得出执行不同步骤所花费的时间也是不一样的。现我们约定执行第
i
步所需花费的时间为
t
i
，其中
t
i
是不依赖于输入规模
n
的常量。
当然，我们必须将某一步骤会执行多次考虑在内。第1步和第3步仅仅执行一次，但是第2步呢？我们必须对
i
和
n
的值比较
n
+1次：即判断
i
≤
n
是否成立
n
次，并且一旦
i
等于
n
+1，我们立即跳出循环。第2
A
步执行
n
次，当
i
从1到
n
变化时，对于每个
i
值，我们执行一次循环体。我们并不能预知我们有多少次将
i
的值赋给了
answer
；这个次数可能是从0次（如果
x
并未出现在数组中时）到
n
次（如果数组中的每个值均等于
x
）的任意一种可能。如果我们要精确地计算执行次数——但是通常我们不会进行那么精确的计算——我们应该认识到第2步会执行两个具有不同循环次数的操作：测试比较
i
和
n
的值会执行
n
+1次，但是自增
i
的值仅仅会执行
n
次。让我们将第2行的操作次数区分开来，其中
表示比较操作的时间，
表示递增操作的时间。同样地，我们将第2A步中判断
A
[
i
]是否等于
x
的操作时间记为
，把
i
值赋给
answer
的操作时间记为
。因此，LINEAR-SEARCH的运行时间介于
和
之间。
现在重写上、下界，并将所有能表示成 n 的倍数的项组合在一起，而将其他项组合在一起，这时我们可以看到运行时间介于 下界
和 上界
之间。观察可得上、下界均可表示成 c . n + d 的形式，其中 c 和 d 均表示不依赖于 n 的常量。也就是说，它们均是关于 n 的 线性函数 。LINEAR-SEARCH的运行时间介于关于 n 的一个线性函数和关于 n 的另一个线性函数之间。
我们用一个特殊符号来表示运行时间大于关于
n
的某线性函数，同时小于关于
n
的某个线性函数（可能与上述线性函数不同）。我们将这样的运行时间表示为Θ（
n
）。Θ是希腊字母theta，并且我们称它为“theta of
n
”或者“theta
n
”。正如第1章所指出的那样，这个符号去除了低阶项
和
n
的系数（对于下界，
n
的系数是
；对于上界，
n
的系数是
。尽管我们用Θ（
n
）来表示运行时间会降低精度，但是它强调了运行时间的增长阶数，同时弱化了不必要的细节。
这个Θ符号适合于任何通用的函数，而不仅仅是那些用来描述算法运行时间的函数，并且它也适用于非线性函数。这个想法正如当我们有两个函数 f （ n ）和 g （ n ），且 n 足够大时， f （ n ）在 g （ n ）的常数倍之内，此时我们称 f （ n ）=Θ（ g （ n ））。因此我们说当 n 足够大时，LINEAR-SEARCH的运行时间小于等于 n 的某个常数倍。
关于Θ符号有一个严格定义，但幸运的是，当使用Θ符号时，我们很少求助于它。我们仅仅关心主阶项，而忽略低阶项和主阶项的常数因子。例如，函数 n 2 /4+100 n +50等价于Θ（ n 2 ）；这个例子中我们忽略了低阶项100 n 和常数项50，并且舍弃了常数因子1/4。尽管当 n 较小时，相对于 n 2 /4，低阶项会起主导作用。一旦 n 超过了400， n 2 /4会超过100 n +50。当 n =1000时，主阶项 n 2 /4等于250000，而低阶项100 n +50仅仅会达到100050；对于 n =2000，此时 n 2 /4等于1000000，而100 n +50等于200050。在算法领域中，有时候我们会滥用符号而写作 f （ n ）=Θ（ g （ n ）），因此我们可以写作 n 2 /4+100 n +50=Θ（ n 2 ）。
现在让我们看看BETTER-LINEAR-SEARCH程序的运行时间。由于我们事先并不知道循环的迭代次数，这一程序比LINEAR-SEARCH更复杂一些。如果 A [1]等于 x ，那么循环只会迭代一次。如果 x 没有在数组中出现，那么循环会迭代 n 次，这是出现得最多的循环次数。每次循环迭代需要花费常量时间，因此我们称 在最坏情况下 ，BETTER-LINEAR-SEARCH在一个包含 n 个元素的数组中进行查找操作需要花费Θ（ n ）时间。为什么要用“最坏情况下”呢？因为我们想要得到运行时间少的算法，最坏情况下发生在对任何可能的输入，一个算法花费最多时间的时候。
在最好情况下，当 A [1]等于 x 时，BETTER-LINEAR-SEARCH仅仅会花费常量时间：将 i 赋值为1，检查 i ≤ n ，此时 A [ i ]= x 为真，并且程序返回 i 的值，即返回1。该时间不依赖于 n 。我们将BETTER-LINEAR-SEARCH在 最好情况下的运行时间 写作Θ（1），因为在最好情况下，它的运行时间在1的常数因子之内。换句话说，最好情况下的运行时间是一个不依赖于 n 的常量。
因此我们看到了不能使用Θ符号来涵盖BETTER-LINEAR-SEARCH运行时间的所有情况。我们不能说运行时间总是Θ（ n ），因为在最好情况下，运行时间是Θ（1）。我们也不能说运行时间总是Θ（1），因为在最坏情况下，运行时间是Θ（ n ）。然而，我们说关于 n 的一个线性函数是所有情况下的一个 上界 ，并且我们用一个符号来表示： O （ n ）。在念这个符号时，我们说“big-ohof n ”或者仅仅称之为“ohof n ”。如果一个函数 f （ n ）是 O （ g （ n ）），即一旦 n 变得非常大， f （ n ）的上界是关于 g （ n ）的常数因子倍，写作 f （ n ）= O （ g （ n ））。对于BETTER-LINEAR-SEARCH，我们可以称在所有情况下，该算法的运行时间均满足 O （ n ）；尽管它的运行时间可能会比关于 n 的某个线性函数运行时间好，但是它一定不会比关于 n 的所有线性函数运行时间都差。
我们使用 O 符号来表示该运行时间从不会比关于 n 的某个函数的常量倍 差 ，但是如何表示不会比关于 n 的某个函数的常量倍 好 呢？这是一个下界问题，此时我们使用Ω符号，这与 O 符号的含义恰恰相反：如果 f （ n ）是Ω（ g （ n ）），即一旦 n 变得非常大时， f （ n ）的下界是 g （ n ）的常数倍，写作 f （ n ）=Ω（ g （ n ））。由于 O 符号给出了上界，Ω符号给出了下界，Θ符号既给出了上界，又给出了下界，我们能推断出 f （ n ）是Θ（ g （ n ）），当且仅当 f （ n ）是 O （ g （ n ））且 f （ n ）是Ω（ g （ n ））。
我们能对BETTER-LINEAR-SEARCH的运行时间给出一个满足所有情况的下界：在所有情况下该运行时间均是Ω（1）。当然，那是一个相对较弱的声明，我们知道对于任何输入的任何算法均至少需要花费常量时间。我们并不会经常使用Ω符号，但是它偶尔也会派上用场。
Θ符号、 O 符号和Ω符号这几个符号均是 渐近符号 。因为这些符号记录了随着变量近似趋向于无穷大时函数的增长趋势。所有这些渐近符号均使得我们去掉了低阶项和高阶项的常数因子，以便能够淡化不必要的细节而专注于主要方面：函数是如何随着 n 增长而变化的。
现在让我们转向讲述SENTINEL-LINEAR-SEARCH程序。正如BETTER-LINEAR-SEARCH一样，循环的每次迭代均需要花费常量时间，并且最少会执行1次迭代，最多执行 n 次迭代。SENTINEL-LINEAR-SEARCH和BET-TER-LINEAR-SEARCH的最大不同是，SENTINEL-LINEAR-SEARCH每次迭代花费的时间小于BETTER-LINEAR-SEARCH每次迭代花费的时间。两者在最坏情况下均需要花费线性时间，但是SENTINEL-LINEAR-SEARCH的常数因子更小一些。尽管我们设想SENTINEL-LINEAR-SEARCH在实际编程条件下运行速度更快，但那也仅仅可能是因为它的常量因子较小引起的。当我们使用渐近符号来表示BETTER-LINEAR-SEARCH和SENTINEL-LINEAR-SEARCH的运行时间时，它们是相等的，即在最坏情况下均是Θ（ n ），在最好情况下均是Θ（1），满足所有条件时均为 O （ n ）。