本节书摘来自华章出版社《算法基础：打开算法之门》一书中的第2章，第2.2节，作者 ［美］托马斯 H 科尔曼（Thomas H Cormen），更多章节内容可以访问云栖社区“华章计算机”公众号查看

2.2 如何描述运行时间

让我们回顾一下LINEARSEARCH程序并计算它的运行时间。回顾第1章的知识可得，运行时间可以表示成一个关于输入规模的函数。这里，输入是一个包含n个元素的数组A，元素数目n，及要查找的值x。随着数组中元素规模的增加，n本身的大小和x的值对运行时间影响不大——毕竟，n仅仅是一个简单的整数且x仅仅可能与数组的n个元素中的某个元素值一样大——因此，这里所提到的输入规模n指的是数组A中元素的数目。

为了表示完成一项任务所花的时间，我们必须做一些简单的假设。我们将假定每步单独的操作——无论它是一个算术运算（例如加、减、乘、除）、比较、变量赋值、给数组标记索引操作，或者是程序调用、从程序中返回结果操作——均会花掉不依赖于输入规模的固定时间。如果对实际的计算机体系结构有一点了解，那么你可能知道存取一个指定变量或者访问数组元素的时间并不一定是固定的，因为它可能取决于变量/数组元素是否在缓存、主存，或者在虚拟存储系统的磁盘外存上。某些精密的计算机模型也将这些因素考虑在内，但是只通过假定所有变量和数组项均存在主存中，且存取这些元素均需要同样的时间就足以达到很好的效果了。操作不同，各个操作所花费的时间可能也不同，例如除法操作可能比加法操作会花更长的时间。但是当一个步骤仅仅是由多个简单操作叠加而成时，该步骤会花费常量时间。由于各个步骤中所执行的操作所花费的时间不同，且根据第1章中所列举出的各种外在因素的影响可以得出执行不同步骤所花费的时间也是不一样的。现我们约定执行第i步所需花费的时间为ti，其中ti是不依赖于输入规模n的常量。当然，我们必须将某一步骤会执行多次考虑在内。第1步和第3步仅仅执行一次，但是第2步呢？我们必须对i和n的值比较n+1次：即判断i≤n是否成立n次，并且一旦i等于n+1，我们立即跳出循环。第2A步执行n次，当i从1到n变化时，对于每个i值，我们执行一次循环体。我们并不能预知我们有多少次将i的值赋给了answer；这个次数可能是从0次（如果x并未出现在数组中时）到n次（如果数组中的每个值均等于x）的任意一种可能。17如果我们要精确地计算执行次数——但是通常我们不会进行那么精确的计算——我们应该认识到第2步会执行两个具有不同循环次数的操作：测试比较i和n的值会执行n+1次，但是自增i的值仅仅会执行n次。让我们将第2行的操作次数区分开来，其中t′2表示比较操作的时间，t″2表示递增操作的时间。同样地，我们将第2A步中判断A［i］是否等于x的操作时间记为t′2A，把i值赋给answer的操作时间记为t″2A。因此，LINEARSEARCH的运行时间介于
和

之间。现在重写上、下界，并将所有能表示成n的倍数的项组合在一起，而将其他项组合在一起，这时我们可以看到运行时间介于下界
和上界
之间。观察可得上、下界均可表示成cn+d的形式，其中c和d均表示不依赖于n的常量。也就是说，它们均是关于n的线性函数。LINEARSEARCH的运行时间介于关于n的一个线性函数和关于n的另一个线性函数之间。我们用一个特殊符号来表示运行时间大于关于n的某线性函数，同时小于关于n的某个线性函数（可能与上述线性函数不同）。我们将这样的运行时间表示为Θ（n）。Θ是希腊字母theta，并且我们称它为“theta of n”或者“theta n”。正如第1章所指出的那样，这个符号去除了低阶项（t1+t′2+t3）和n的系数（对于下界，n的系数是t′2+t″2+t′2A；对于上界，n的系数是t′2+t″2+t′2A+t″2A）。尽管我们用Θ（n）来表示运行时间会降低精度，但是它强调了运行时间的增长阶数，同时弱化了不必要的细节。这个Θ符号适合于任何通用的函数，而不仅仅是那些用来描述算法运行时间的函数，并且它也适用于非线性函数。这个想法正如当我们有两个函数f(n)和g(n)，且n足够大时，f(n)在g(n)的常数倍之内，18此时我们称f(n)=Θ（g(n)）。因此我们说当n足够大时，LINEARSEARCH的运行时间小于等于n的某个常数倍。关于Θ符号有一个严格定义，但幸运的是，当使用Θ符号时，我们很少求助于它。我们仅仅关心主阶项，而忽略低阶项和主阶项的常数因子。例如，函数n2/4+100n+50等价于Θ（n2）；这个例子中我们忽略了低阶项100n和常数项50，并且舍弃了常数因子1/4。尽管当n较小时，相对于n2/4，低阶项会起主导作用。一旦n超过了400，n2/4会超过100n+50。当n=1000时，主阶项n2/4等于250000，而低阶项100n+50仅仅会达到100050；对于n=2000，此时n2/4等于1000000，而100n+50等于200050。在算法领域中，有时候我们会滥用符号而写作f(n)=Θ（g(n)），因此我们可以写作n2/4+100n+50=Θ（n2）。现在让我们看看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）。在念这个符号时，19我们说“bigoh of n”或者仅仅称之为“oh of 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和BETTERLINEARSEARCH的最大不同是，SENTINELLINEARSEARCH每次迭代花费的时间小于BETTERLINEARSEARCH每次迭代花费的时间。两者在最坏情况下均需要花费线性时间，但是SENTINELLINEARSEARCH的常数因子更小一些。尽管我们设想SENTINELLINEARSEARCH在实际编程条件下运行速度更快，但那也仅仅可能是因为它的常量因子较小引起的。当我们使用渐近符号来表示BETTERLINEARSEARCH和SENTINELLINEARSEARCH的运行时间时，20它们是相等的，即在最坏情况下均是Θ（n），在***情况下均是Θ（1），满足所有条件时均为O（n）。