算法基础（第5版）——1.2　开发高效算法的重要性

前面曾经提到，无论计算机变得多么快速，内存变得多么廉价，效率永远都是重要的考虑因素。接下来，我们通过对比同一问题的两种算法来说明其原因。 1.2.1　顺序查找与二分查找的对比 前面曾经提到，在电话簿中查找姓名的方法是一种经过修改的二分查找，它通常要远快于顺序查找。下面将对比这两种方法的算法，以说明二分查找法要快多少。 我们已经编写了完成顺序查找的算法，即算法1.1。在一个非递减顺序数组中进行二分查找的算法类似于用大拇指前后翻动电话簿。也就是说，假定正在查找x，算法首先将x与数组的中间项进行对比。如果相等，则算法完成。如果x小于中间项，则x必然在数组的前半部分（如果存在的话），算法将对数组的前半部分重复该查找过程。（也就是说，将x与数组前半部分的中间项进行比较，等等。）如果x大于数组的中间项，则对数组的后半部分重复查找过程。一直重复此过程，直到找出x，或者确认x不在数组中为止。这一方法的算法如下。 算法1.5　二分查找 问题：判断x是否在一个包含n个键的有序数组S中。 输入：正整数n；有序（非递减顺序）键数组S，其索引范围为1至n；键x。 输出：location，x在S中的位置（如果x不在S中，则为0）。 void binsearch (int n, const keytype S[], keytype x, index& location) { index low, high, mid; low = 1; hign = n; location = 0; while (low <= high && location == 0){ mid = ⌊(low + high)/2⌋; if (x = = S[mid]) location = mid; else if (x < S[mid]) high = mid - 1; else low = mid + 1; } } 我们来对比顺序查找与二分查找所做的工作。重点确定每种算法执行的比较次数。如果数组S包含32项，且x不在数组中，则算法1.1（顺序查找）需要将x与所有32项进行比较后，才能确定x不在数组中。一般情况下，对于一个大小为n的数组，顺序查找需要完成n次比较才能确定x不在该数组中。显然，在搜索一个大小为n的数组时，这是顺序查找所执行的最大比较次数。也就是说，如果x在数组中，则比较次数不大于n。 下面考虑算法1.5（二分查找）。每执行一遍while循环，会将x与S[mid]比较两次（找到x时除外）。在用高效汇编语言实现该算法时，每执行一遍while循环，仅将x与S[mid]比较一次，比较结果将确定条件代码，然后根据条件代码的取值执行适当的跳转。这意味着每执行一遍while循环，仅将x与S[mid]比较一次。我们假定算法就是以这种方式实现的。在这一假设条件下，图1-1表明，对于一个大小为32的数组，若x大于其中所有项目，该算法将执行6次比较。注意，6 = lg32 + 1。这里的lg是指log2。在算法分析中经常会遇到log2，所以我们为它保留了特殊符号lg。你应当相信，二分查找最多只需要执行这么多的比较次数。也就是说，如果x在数组中，或者x小于数组中的所有项目，或者x在两个数组项目之间，所执行的比较次数都不会超过x大于所有数组项目时的次数。 图1-1　对于一个大小为32的数组，当x大于其中所有项目时，二分查找法用来与x进行比较的数组项目。这些项目的编号就是它们与x的比较顺序 假设将数组大小加倍，使其包含64个项目。二分查找只会增加一次比较，因为第一次比较就将数组减半，得到一个大小为32的待查子数组。因此，对于一个大小为64的数组，当x大于其中所有项目时，二分查找执行7次比较。注意，7 = lg64 + 1。一般情况下，数组大小每加倍一次，只需要增加一次比较。因此，若n是2的幂，对于一个大小为n的数组，若x大于其中所有项目，则二分查找执行的比较次数为lgn +1。 表1-1对比了当x大于数组中所有项目时，顺序查找和二分查找对于不同n值所执行的比较次数。当数组包含大约40亿个项目时（大约是世界上的人口数量），二分查找只执行33次比较，而顺序查找则将x与所有40亿个项目进行了比较。即使计算机能在1 纳秒（一秒的十亿分之一）内完成一次while循环，顺序查找也需要4秒钟才能确定x不在数组中，而二分查找几乎马上就可以做出判断。对于在线应用程序或者在需要查找许多项目时，这一差别会非常明显。 表1-1　当x大于所有数组项目时，顺序查找和二分查找执行的比较次数 数组大小 顺序查找执行的比较次数 二分查找执行的比较次数 128 1024 1 048 576 4 294 967 296 128 1024 1 048 576 4 294 967 296 8 11 21 33 为方便起见，在前面对二分查找的讨论中，所考虑数组的大小都是2的幂。第2章还会再次讨论二分查找法，将其作为该章主题内容——分而治之方法的一个例子。届时将考虑大小可以为任意正整数的数组。 尽管上面这个查找范例给人们留下了很深刻的印象，但其说服力也并不强，因为顺序查找仍然可以在人的有生之年内完成任务。接下来将研究一个更差的算法，它无法在可接受的时间内完成任务。 1.2.2　斐波那契序列 现在讨论用于计算斐波那契序列第n个项目的算法。斐波那契序列的递归定义如下： 　（n≥2） 计算序列中的前几个项目，可得： 斐波那契序列在计算机科学和数学中有着多种应用。因为斐波那契序列是以递归形式定义的，所以可由定义中得出以下递归算法。 算法1.6　斐波那契序列的第n项（递归） 问题：确定斐波那契序列的第n项。 输入：一个非负整数n。 输出：fib，斐波那契序列的第n项。 int fib (int n) { if (n <= 1) return n; else return fib(n-1)+fib(n-2); } “非负整数”是指大于或等于0的整数，而“正整数”则是指严格大于0的整数。我们以这种方式规定算法的输入，明确指出输入可取哪些值。但是，为避免混乱，算法的表达式中直接将n声明为一个整数。本书中将一直遵循这一约定。 尽管这一算法很容易生成，也很好理解，但其效率却极为低下。图1-2给出了在计算fib(5)时与该算法对应的递归树。树中一个节点处的调用会递归调用其子节点处的调用。例如，为在顶级获得fib(5)，需要fib(4)和fib(3)；为了获得fib(3)，又需要fib(2)和fib(1)，以此类推。如树中所示，因为需要一遍又一遍地计算各个取值，所以这个函数的效率很低。例如，fib(2)被计算了三次。 图1-2　算法1.6计算第5个斐波那契项时的对应递归树 这个算法的效率有多低呢？图1-2中的树显示，为了计算fib(n)（0≤n≤6），该算法计算的项数如下： 显示错误！ 当1≤n≤5时，只需要数一数以fib(n)为根节点的子树中有多少个节点，即可求出前六个值。而在计算fib(6)中的项数时，需要先计算分别以fib(5)和fib(4)为根节点的树中有多少节点，然后再将两者之和加上fib(6)所在的根节点。我们无法由这些数字得到一个类似于二分查找那样的简单表达式。但可以注意到，对于前7个数值，每当n值增加2时，树中的项目数将超过原来的2倍。例如，当n=4时，树中有9项；当n=6时，有25项。我们将T(n)称为n的递归树中的项数。如果n每增加2，项数都会超过原来的2倍，则对于偶数n，可以得到下式： 因为T(0)=1，所以这将意味着T(n)>2n/2。我们用归纳法来证明，即使n不是偶数，上式在n≥2时也是成立的。当n=1时，该不等式不成立，这是因为T(1)=1，它小于21/2。归纳法在附录A的A.3节复习。 定理1.1　若T(n)是与算法1.6对应的递归树中的项数，则当n≥2时， 证明：通过对n进行归纳来完成证明。 归纳基础：因为归纳部分需要前两种情景的结果，所以需要两个基础情景。对于n=2和n=3，图1-2中的递归表明： 归纳假设：做出归纳假设的一种方式是假定该命题对于所有小于n的m值都成立。随后在归纳步骤中证明，由这一假设可以推导出，上述命题对于n也必定成立。下面的证明中采用了此方法。假设对于2≤m<n的m值，有 归纳步骤：必须证明 。T(n)的值等于T(n1)与T(n2)之和再加上一个根节点。因此， 我们已经确认，为求出第n个斐波那契项，算法1.6计算的项数大于2n/2。后面会再次讨论这一结果，以说明该算法是多么低效。但首先来设计一种用于计算第n个斐波那契项的高效算法。回想一下，递归算法的问题就在于会一遍又一遍地计算同一数值。如图1-2所示，在计算fib(5)时，fib(2)被计算了3次。如果在计算一个值时，将其保存在一个数组中，后面再需要它时，就不用再重新计算了。下面的迭代算法就使用了这一策略。 算法1.7　斐波那契序列的第n项（迭代） 问题：确定斐波那契序列的第n项。 输入：一个非负整数n。 输出：fib2，斐波那契序列的第n项。 int fib2 (int n) { index i; int f[0..n]; f[0]=0; if (n > 0) f[1]=1; for (i=2; i<=n; i++) f[i]=f[i-1]+f[i-2]; } return f[n]; } 不用数组f也可以写出算法1.7，因为循环的每次迭代只需要最近两项。但是，使用数组可以表述得更清楚一些。 以上算法在计算fib2(n)时，前n+1项中的每一项都仅计算一次。因此，为求出第n个斐波那契项，它只需要计算n+1个项目。回想一个，算法1.6需要计算超过2n/2个项目来计算第n个斐波那契项。表1-2对比了这些表达式在n取不同值时的结果。执行时间的计算基于一个简化假设：一个项目可以在109秒内计算得出。该表给出了算法1.7在一台假想计算机上计算第n项时所耗费的时间（该计算机计算每项的时间为1纳秒），并给出了执行算法1.7所需要的时间下限。当n为80时，算法1.6至少需要18分钟。当n为120时，它需要超过36年，与人类的寿命相比，这是一个无法忍受的时间。即使可以建造一台快10亿倍的计算机，算法1.6也需要40 000年才能计算出第200项。将第200项的时间除以10亿即可得出这一结果。可以看出，无论计算机变得多么快，算法1.6仍然需要耗费无法忍受的时间，除非是n值非常小。另一方面，算法1.7几乎马上就可以计算出第n个斐波那契项。这一比较结果表明，无论计算机变得多么快，算法的效率都依然是一个重要的考虑因素。 表1-2　算法1.6与算法1.7的比较 n n+1 2n/2 使用算法1.7的执行时间 使用算法1.6的执行时间下限 40 60 80 100 120 160 200 41 61 81 101 121 161 201 1 048 576 1.1×109 1.1×1012 1.1×1015 1.2×1018 1.2×1024 1.3×1030 41 ns* 61 ns 81 ns 101 ns 121 ns 161 ns 201 ns 1048 μs† 1秒 18分 13天 36年 3.8×107年 4×1013年 * 1 ns = 109秒。 † 1 μs = 106秒。 算法1.6是一种分而治之算法。回想一下，分而治之方法为有序数组的查找问题提供了一种非常高效的算法（算法1.5：二分查找）。如第2章所示，分而治之方法会为某些问题给出非常高效的算法，但对其他一些问题，却会给出非常低效的算法。我们为计算第n个斐波那契项给出的高效算法（算法1.7）是动态规划方法（dynamic programming approach）的一个例子，这种方法是第3章的主题。可以看出，最佳方法的选择才是本质所在。 前面已经表明，算法1.6计算的项数非常大，至少为指数级，那还会更糟糕吗？答案是否定的。利用附录B中的技术，有可能给出项数的准确公式，该公式是n的指数函数。有关斐波那契序列的深入讨论，请参阅附录B中的例B.5和例B.9。