下载掌阅APP，畅读海量书库
立即打开
影响程序运行时间的因素有：
● 程序采用的算法；
● 计算机软硬件系统的性能；
● 编译器生成的目标代码的质量；
● 问题规模；
● 数据的分布情况。
同一个问题往往可以采用不同的算法求解，例如去书店购买某本文学小说，有两种方式：第一种，在书店里挨个书柜寻找；第二种，直接去文学小说书柜寻找。显然，第一种方式的寻找时间长，而第二种方式的寻找时间要短很多。因此，程序采用的算法不同，其运行时间也大相径庭。
当在运算速度不同的硬件上运行同一个程序时，即便输入同样的数据，其所需的运行时间也会不同。即使硬件环境一样，程序运行在不同编译器的软件环境中，生成的可执行代码是不同的，运行时间也不一样。因此，运行时间不能说明程序采用的算法的优劣。
算法的时间性能应该与运行算法的计算机的软硬件系统无关，在算法分析中通常用运算量衡量。算法所需的运算量与所处理问题的规模之间的关系称为算法的时间复杂度。优化算法的时间复杂度的关键是降低所需的运算量。
算法的运算量除了与问题规模有关，还与被处理的数据的分布情况有关。在实际应用中，很难用单一指标描述算法的时间性能。算法分析中，通常用最好情况、最坏情况及平均情况时间复杂度描述不同的数据分布情况下的时间复杂度。例如，火车票管理系统中有 n 个车次存储于数组中，现要查找是否存在某个车次。假设算法从第一个车次开始依次往后查找，直到找到了该车次或找遍了整个数组也没有找到该车次。如果被查找的车次出现在第一个位置，则比较一次就找到了。在这种情况下，算法所需的时间最短，这就是最好情况的时间复杂度。如果被查找的车次出现在最后或根本没有出现，则需要比较所有车次，即比较 n 次。在这种情况下，算法所需的运行时间最长，这就是最坏情况的时间复杂度。如果每个车次被查找的概率相等，则经过多次查找后，平均需要查找 n /2次，这就是平均情况的时间复杂度。
假设有一组存储在数组array中的正整数，要求设计一个算法，求数组中的最大值与正整数 d 的乘积。代码清单1-1展示了这一问题的两个算法实现。函数max1(int array[], int size, int d)先对数组元素逐一乘d，再求数组中的最大元素；而函数max2 (int array[], int size, int d) 先求数组中的最大值，再将其乘d。对于任意的输入，函数max1()的运算量显然比max2()大，因为max1()多运行了第一个for循环，即多做了 n −1次乘法和 n 次赋值。因此，在软硬件环境、问题规模、数据分布均相同的情况下，max1()的运行时间一定比max2()长，也就是说max2()的时间性能更好一些。
代码清单1-1 函数max1()与max2()的实现
int max1(int array[], int size, int d) {
int max = 0, i;
for (i = 0; i < size;++i) array[i] *= d;
for (i = 0; i < size;++i)
if (array[i] > max) max = array[i];
return max;
}
int max2(int array[], int size, int d) {
int max = 0, i;
for (i = 0; i < size;++i)
if (array[i] > max) max = array[i];
return max * d;
} 从上述讨论明显看出，评价算法的性能时并不需要计算精确的运算时间，只要能反映求解相同问题的不同算法的运算量之间的差异即可。通常的做法如下：
（1）选择一种或几种简单语句作为标准操作，将标准操作作为一个运算单位；
（2）确定每个算法在给定的输入下共执行了多少次标准操作，将该数值作为算法的运算量。
对于代码清单1-1中的例子，如果选择乘法、赋值和条件判断作为标准操作，则当输入的数组值为1,3,5，且 d =10时，max1()执行了3次乘法（第一个for循环体）、14次赋值（第一个for循环的循环控制行中的i = 0、++i分别执行了1次、3次赋值，循环体也执行了3次赋值；第二个for循环也一样）、11次比较（第一个和第二个for循环体的循环控制行中的i < size均执行了4次；for循环体执行了3次），共28次标准操作。同样，max2()执行了1次乘法、7次赋值、7次比较，共15次标准操作。显然，max2()的时间性能优于max1()。
如何计算一个算法随问题规模变化的运算量？先来分析一下max1()在最坏情况下的运算量。假设数据规模为 n ，首先看第一个for循环。在循环控制行中，i = 0执行1次，i < size执行 n +1次，++i执行 n 次。循环体执行 n 次，在每个循环周期中执行1次乘法、1次赋值。因此第一个for循环体总的运算量为1+( n +1)+ n + n ×2 = 4 n +2。再来看第二个for循环体。在循环控制行中，i = 0执行了1次，i < size执行了 n +1次，++i执行了 n 次，循环体执行1次比较，在最坏情况下，还要执行1次赋值。因此，第二个for循环体的总运算量为1+( n +1)+ n + n ×2 = 4 n +2。max1()在最坏情况下的总运算量是8 n +4。同理，可找出最好情况下运算量与问题规模之间的关系。
一般来说，算法的运行时间函数是一个很复杂的函数，而且求解同一问题的算法也不止一种，自然相应的运行时间函数也不一样。那么，如何比较不同算法的运行时间函数，并选择一个好的算法解决特定问题呢？这项工作不是那么简单。
运行时间与数据规模有关，例如对于两个算法 f 1 和 f 2 ，其运行时间函数分别为 T 1 ( n ) = n 2 +225和 T 2 ( n ) = 2 n 2 。当 n <15时， T 1 ( n )> T 2 ( n )，即算法 f 1 的运行时间函数值比 f 2 大；当 n >15时， T 1 ( n )< T 2 ( n )，即算法 f 1 的运行时间函数值比 f 2 小，那么到底是算法 f 1 好还是算法 f 2 好？
当问题规模很小时，运行时间不会影响算法的时间性能。算法的时间性能主要考虑问题规模很大时，运行时间随问题规模的变化趋势。因此，问题规模较小时，运行时间可以忽略不计，只考虑问题规模大到一定程度后的情况。例如上述算法 f 1 和 f 2 ，我们认为算法 f 1 的时间性能优于 f 2 的时间性能。因为当 n >15时，算法 f 2 的运行时间函数值总是大于算法 f 1 的运行时间函数值。
当问题规模很大时，算法的运行时间函数也会出现很多形式，此时又如何衡量算法的优劣呢？这个问题比上一个问题更复杂，这里略做简化，不考虑具体的运行时间函数，只考虑运行时间函数的数量级。这种方法称为渐近表示法。最常用的渐近表示法是大O表示法。
定义1-1 （大O表示法）如果存在两个正常数 c 和 N 0 ，使得当 n ≥ N 0 时有 T ( n )≤ cF ( n )，则记为 T ( n )= O ( F ( n ))。
例1-1 设 T ( n )=( n +1) 2 。当 N 0 =1及 c =4时， T ( n )≤ cn 2 成立。因此， T ( n )= O ( n 2 )。
例1-2 设 T ( n )=2 n 3 +3 n 2 。当 N 0 =0及 c =5时， T ( n )≤ cn 3 成立。因此， T ( n )= O ( n 3 )。
大O表示法给出了算法运行时间随数据规模增长的上界，亦称渐近时间复杂度，简称时间复杂度。大O表示法不需要计算运行时间的精确值，只需要给出一个数量级，表示当问题规模很大时，对算法运行时间的增长影响最大的函数项（主项），忽略对问题的时间复杂度产生较小影响的低阶项。因此，在选择 F ( n )时，通常选择运行时间函数的最高次项，忽略低次项及系数。表1-1给出了常用的时间复杂度函数及其名称。
表1-1 常用的时间复杂度函数及其名称
[1]若无特殊说明，本书中的log均表示以2为底数的对数。
表1-1中的常数级时间复杂度表示算法的运行时间与问题规模无关，无论问题规模怎样，算法总是执行有限个标准操作。
时间复杂度为多项式的算法称为多项式时间算法，时间复杂度为指数函数的算法称为指数时间算法。最常见的多项式时间算法的时间复杂度之间的关系为 O (1) < O (log n ) < O ( n ) < O ( n log n ) < O ( n 2 ) < O ( n 3 )，即时间复杂度为 O (1)的算法是最好的算法，其次是时间复杂度为 O (log n )的算法。指数时间算法的时间复杂度之间的关系为 O (2 n ) < O ( n !) < O ( n n )。多项式时间算法要比指数时间算法好。
从大O表示法的定义（定义1-1）可以看出，大O表示法只是表示算法运行时间函数的上界，并没有考虑这个函数与上界的接近程度。在实际计算时，应选择算法运行时间函数的最小上界。
为了更精确地表示算法的时间性能，算法分析领域还定义了其他3种与大O表示法相关的时间复杂度的渐进表示法，而且本书后续章节偶尔会用到这几种方法。
定义1-2 （大Ω表示法）如果存在两个正常数 c 和 N 0 ，使得当 n ≥ N 0 时有 T ( n )≥ cF ( n )，则记为 T ( n )= Ω ( F ( n ))。
定义1-3 （大Ө表示法）当且仅当 T ( n )= O ( F ( n ))，且 T ( n )= Ω ( F ( n ))，则记为 T ( n )= Ө ( F ( n ))。
定义1-4 （小o表示法）当且仅当 T ( n )= O ( F ( n ))，且 T ( n )≠ Ө ( F ( n ))，则记为 T ( n )= o ( F ( n ))。
大O表示法说明 T ( n )的增长率小于或等于 F ( n )的增长率，即 F ( n )为 T ( n )的上界。大Ω表示法说明 T ( n )的增长率大于或等于 F ( n )的增长率，即 F ( n )为 T ( n )的下界。大Ө表示法说明 T ( n )的增长率等于 F ( n )的增长率，即 T ( n )的上界与下界相等。小o表示法说明 T ( n )的增长率严格小于 F ( n )的增长率，即 T ( n )的上界与下界不等。
算法的时间复杂度的计算可以按照代码清单1-1的分析方法，首先定义算法的标准操作，然后计算算法的标准操作次数，这样就可以得到一个随问题规模变化的标准操作次数的函数。最后取出函数的主项，作为其时间复杂度的大O表示。但这种计算方法比较烦琐，下面将介绍一些时间复杂度的简化计算方法。我们先引入两个常用定理。
定理1-1 求和定理：假定 T 1 ( n )、 T 2 ( n )分别是程序P 1 、P 2 的运行时间函数，且 T 1 ( n )属于 O ( f ( n ))，而 T 2 ( n )属于 O ( g ( n ))。那么，先运行P 1 ，再运行P 2 的总运行时间是 T 1 ( n )+ T 2 ( n )= O (MAX( f ( n ), g ( n )))。
证明：根据定义1-1，对于某些正常数 c 1 、 n 1 及 c 2 、 n 2 ，根据已知条件，可得：
当 n ≥ n 1 时， T 1 ( n )≤ c 1 f ( n )成立；
当 n ≥ n 2 时， T 2 ( n )≤ c 2 g ( n )成立。
设 n 1 和 n 2 之间的最大值为 n 0 ，即 n 0 =MAX( n 1 , n 2 )。
那么，当 n ≥ n 0 时， T 1 ( n )+ T 2 ( n )≤ c 1 f ( n )+ c 2 g ( n )成立。因此， T 1 ( n )+ T 2 ( n )≤( c 1 + c 2 )MAX( f ( n ), g ( n ))。于是，定理得证。
定理1-2 求积定理：如果 T 1 ( n )和 T 2 ( n )分别属于 O ( f ( n ))和 O ( g ( n ))，那么 T 1 ( n )× T 2 ( n )属于 O ( f ( n )× g ( n ))。
证明：根据已知条件，当 n ≥ n 1 时， T 1 ( n )≤ c 1 f ( n )成立。当 n ≥ n 2 时， T 2 ( n )≤ c 2 g ( n )成立。其中 c 1 、 n 1 及 c 2 、 n 2 都是正常数。因此，当 n ≥MAX( n 1 , n 2 )时， T 1 ( n )× T 2 ( n )≤ c 1 c 2 f ( n ) g ( n )，说明 T 1 ( n )× T 2 ( n )属于 O ( f ( n )× g ( n ))。
定理1-1和定理1-2为时间复杂度的计算提供了很大便利。由这两个定理可以得到以下5条简化的计算规则。
规则1。每个简单语句，如赋值语句、输入/输出语句，它们的运行时间与问题规模无关，在每个计算机系统中的运行时间都是一个常量，因此时间复杂度为 O (1)。
规则2。对于条件语句，if <条件> then <语句> else <语句>的运行时间为进行条件判断的代价，时间复杂度一般为 O (1)，再加上运行then后面的语句的代价（若条件为真），或运行else后面的语句的代价（若条件为假），时间复杂度为MAX( O (then子句), O (else子句))。
规则3。对于循环语句，运行时间是循环控制行和循环体运行时间的总和。循环控制行的作用一般是进行一个简单的条件判断，不会占用大量的时间，因此时间复杂度为 O (循环次数× O (循环体))。
规则4。对于嵌套循环语句，在外层循环的每个循环周期，内层循环都要运行它的所有循环周期，因此，可用求积定理计算整个嵌套循环语句的时间复杂度，即时间复杂度为 O ( O (内层循环体)×外层循环的循环次数)。例如，以下程序
for (i=0; i<n; i++)
for (j=0; j<n; j++)
for (k=0; k<n; k++) s++;的时间复杂度为 O ( n 3 )。
规则5。连续语句的时间复杂度是利用求和定理把这些连续语句的时间复杂度相加而得到的。例如，以下程序
for (i=0; i<n; i++) a[i]=0;
for (i=0; i<n; i++)
for (j=0; j<n; j++) a[i]= i+j;由两个连续的循环组成。第一个循环的时间复杂度为 O ( n )，第二个循环的时间复杂度为 O ( n 2 )。根据求和定理，整个程序的时间复杂度为 O ( n 2 )。
有了这些简化的计算规则后，计算算法的时间复杂度就简单了。没有必要像分析max1()的时间性能那样统计所有标准操作的次数，而只需要找出最复杂、运行时间最长的程序段。在max1()中，最复杂的程序段是两个循环，这两个循环的时间复杂度都为 O ( n )，因此整个程序的时间复杂度是 O ( n )。