算法的效率

专题二算法的效率评价一个算法的效率主要是考察算法执行时间的情况。可以在相同的规模下，根据执行时间的长短来评价一个算法的优劣。一个算法的好坏对计算机的效能影响有多大呢？我们来做这样一个比较，假设有两台计算机分别是计算机A和计算机B，计算机A的运算处理速度比计算机B大约快50倍。以求解“百钱买百鸡”（“鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一。百钱买百鸡。问鸡翁、母、雏各几何？”）为例子，设鸡翁为x只，鸡母为y只，鸡雏为z只。算法A：把公鸡、母鸡、小鸡的枚举范围都是1～100；算法B：经粗略计算公鸡的枚举范围为1～20，母鸡的枚举范围为1～33，而小鸡的枚举范围应是100－x－y。在计算机A上运行算法A程序，在计算机B上运行算法B程序，两台计算机谁先把结果运算出来呢？算法A的程序代码如下：Forx=1To100Fory=1To100Forz=1To100If(x+y+z=100)And(5*x+3*y+z/3=100)ThenList1.AddItemStr(x)++Str(y)++Str(z)EndIfNextzNextyNextx算法B程序代码如下：Forx=1To20Fory=1To33Z=100-x-yIf5*x+3*y+z/3=100ThenList1.AddItemStr(x)++Str(y)++Str(z)EndIfNextyNextx运算结果是计算机B先把结果运算出来。为什么会这样呢？我们来分析一下，算法A需要执行100×100×100=1000000次内循环，而算法B只需要执行20×33=660次内循环，虽然计算机A比计算机B快50多倍，但还是计算机B先求得计算结果。一个好的算法可以算得更快。什么样的算法是好算法呢？通常从时间复杂度和空间复杂度两方面来评价，在这里我们主要讨论时间复杂度。通常我们把算法的基本操作执行的次数作为算法的时间量度T(n)=O(f(n))，表示随着规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称时间复杂度，估算时按该算法对各种输入情况的平均值来考虑。在最坏情况下的复杂度和平均情况下的复杂度是评估算法两种衡量标准。在排序算法中，我们学习了冒泡排序和交换排序，这两种算法的效率如何呢？下面我们来进行讨论。算法的基本操作主要是比较语句和交换两个变量值的赋值语句。冒泡排序（bubblesort）是在一列数据中把较小的数据逐次向上推移的一种技术，它和气泡从水中往上冒的情况有些类似，它把待排序的n个元素的数组看成是垂直堆放的一列数据，从最下面的一个元素起，自下而上地比较相邻两个元素中的数据，将较小的数据换到上面的一个元素中。当第一遍加工完成时，最小的数据已经上升为第一个元素的数据。然后对余下的n-1个元素重复上述处理过程，直至最后进行余下两个数据的比较和交换。在冒泡排序实现过程中，一般地，对于数组d(1)、d(2)、d(3)、…、d(n)第1遍，比较d(j)、d(j-1)，j=n，n-1，…4，3，2，需要比较关键字n-1次；第2遍，比较d(j)、d(j-1)，j=n，n-1，…4，3，需要比较关键字n-2次；……第n-1遍：比较d(j)、d(j-1)，j=n，需要比较关键字1次。所以共需比较关键字(n-1)+(n-2)+…+1=n(n-1)/2次。在最好情况下移动次数为0次（原数列已经按从小到大排好序），在最坏情况下移动次数为3n(n-1)/2次（原数列是按从大到小排列的，而输出是从小到大排序，每次比较都要交换数据，每次交换数据都要执行三条赋值语句，故为3倍的比较次数）。最坏情况是例如原数列是5，4，3，2，1，现要求从小到大排序。冒泡排序程序执行过程数组数据变化如下：第1遍：[54321]、[54312]、[54132]、[51432]、[15432]，移动4*3次；第2遍：[15432]、[15423]、[15243]、[12543]，移动3*3次；第3遍：[12543]、[12534]、[12354]，移动2*3次第3遍：[12354]、[12345]，移动1*3次共移动3*（4+3+2+1）=3*5*(5-1)/2=30次冒泡算法的平均移动次数为3(n2-n)/4，随着n的增大，在这个多项式中主导整个函数式且成长最快的是n2项（在多项式中主导项是具有最高次的那一项），可以得到算法的时间复杂度与n2同阶（同一个数量级），记作O(n2)，“O”表示数量级，读作“n平方阶”。选择排序（直接选择排序、selectionsort）是对冒泡排序算法的改进，它的方法是在参加排序的所有数组元素中找出最小（或最大）数据的元素，使它与第一个元素中的数据相互交换位置。然后再在余下的元素中找出最小（或最大）数据的元素，与第二个元素中的数据交换位置，以此类推，直到所有元素成为一个有序的序列。它减少了交换的次数。在直接选择排序过程中，共需比较关键字n(n-1)/2次，在最好情况下移动次数为0次（原数列已经按要求排好），在最坏情况下为3(n-1)次（外循环执行n-1次，每次移动有三条赋值语句，固为3(n-1)次）。最坏情况例如原数列为5，1，2，3，4，现要求从小到大排序。选择排序程序执行过程数组数据变化如下：第1遍：[51234]、[15234]，比较4次，移动3次；第2遍：[15234]、[12534]，比较3次，移动3次；第3遍：[12534]、[12354]，比较2次，移动3次；第3遍：[12354]、[12345]，比较1次，移动3次共比较4+3+2+1=5*(5-1)/2=10次，移动3*4=12次。由此可知，比较关键字的次数n(n-1)/2次，平均移动次数3(n-1)/2次，随着n的增大，在多项式中主导项是n2，也就是说与n2同价，算法的时间复杂度也是O(n2)。因此，冒泡排序、直接选择排序算法比较简单，但所需要的时间代价都比较大，都为O(n2)。因此在待排序数列长度n较小时，适合使用，当数值n较大，并且没有规律时，可采用快速排序O(nlog2n)、堆排序O(nlog2n)。在查找算法中，顺序查找和对分查找的算法的效率又是如何呢？顺序查找法是依次从头找到尾，它对查找数列没有有序性要求。对在n个数据中进行查找，在最好情况下，查找次数为1（需要查找的键正好是第一个），在最坏情况下，查找次数为n（需要查找的键正好是最后一个），按概率的平均查找次数为(n+1)/2次，时间复杂度为O(n)，顺序查找的效率比较低，适合数据量比较小的情况下。对分查找要求查找的数据必须是已经有序排列的且知道是增序或减序，查找时首先与序列中间位置上的元素进行比较，如果中间位置上的元素与查找键不同，根据查找键的值是大于还是小于中间位置上的元素和数组是增序还是降序排序来确定是在数组的前半部分还是后半部分继续进行查找；在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。在最好情况下，查找次数为1（需要查找的键恰好是中间位置），在最坏情况下，查找次数最多为┌log2(n+1)┐（不小于log2(n+1)的最小整数），时间复杂度为O(log2n)，当n较大时，对分查找的效率比顺序查找高出许多。常见时间复杂度，按数量级递增排列依次为：O(1)O(log2n)O(n)O(nlog2n)O(n2)O(nk)O(2n)O(kn)O(n!)各时间复杂度计算量比较（假设k=3）：n=10n=20n=100n=1000n=106O(log2n)3.324.326.649.9619.9O(n)10201001000106O(nlog2n)33.286.46649.96x1031.99x107O(n2)1004001041061012O(nk)100080001061091018O(2n)1024104857610301030110301030O(kn)590493486784401104710477极大O(n!)36288002.43x101810157102567极大O(1)表示时间复杂度与问题规模n无关。例如：我们计算S=1+2+3+…+n时，使用算法：Form=1tons=s+mNextm时间复杂度为O(n)，而如果我们使用公式s=n*(n+1)/2来运算，则时间复杂度就是O(1)。在汉诺塔问题中，移动次数会随着盘片n的增加而快速增长，次数是2n-1次，它的时间复杂度是O(2n)。通常我们认为，具有指数阶量级的算法是实际不可计算的，而量级低于2次方阶的算法是好的、高效的。因此当我们处理很大规模的问题时，我们必须考虑算法的好坏对计算机效能的影响，降低算法的时间复杂度比选择高性能的计算机更显得重要。那么是否是所有的问题我们都能设计出高效的算法来求解呢？很可惜，答案是否定的。我们把一个问题的答案只有“是”或“否”的问题称为判定问题。例如哥尼斯堡七桥问题。18世纪在哥尼斯堡城，现在是俄罗斯加里宁格勒的加里宁格勒市。在城市的普莱格尔河上有7座桥，将河中的两个岛和河岸连结，如图6.1左图所示（字母Ａ、Ｂ、Ｃ、Ｄ分别表示岛和河岸）。当时那里的居民热衷于一个难题：一个散步者从其住所出发，怎样才能一次走遍七座桥，每座小桥只走一次，最后返回到出发点？图6.1哥尼斯堡城的七桥问题谁都愿意试一试，它的答案是“是”，还是“否”呢？但谁也找不出答案，问题最后由欧拉解决了，他猜想这样的路根本不存在，1736年，他证明了他的猜想。他用结点Ａ、Ｂ、Ｃ、Ｄ表示岛和河岸，用连线来表示桥，由此得到一个由七条线组成的图形（图6.1右图），这样，哥尼斯堡七桥问题就变成了一笔画问题：能不能一笔画出这个图形，并且能最后返回到起点。欧拉证明了一幅点－弧线图能一笔画的充要条件是：图中不存在度数（连接该顶点的边数）为０的顶点或者存在0个或2个度数为奇数的顶点。从图6.1中可知顶点A、B、C、D的度数分别为5、3、3、3，存在4个度数为奇数的顶点，所以是不能一笔画的。这种对于给定的一个判定问题，若存在一个求解该问题的阶数为多项式时间的算法，则称该问题是多项式可解问题，多项式可解问题的集合称为P类问题。下图6.2能否一笔画呢？图6.2对应七桥问题的一笔画图形先计算各顶点的度数，各顶点度数如下表：结点ＡＢＣＤＥＦＧ度数６４４６３４５因为只存在2个度数为奇数的顶点Ｅ、Ｇ，所以可以一笔画。一笔画时，用其中一个度数为奇数的顶点作为起点，另一个必定是终点，如果是0个度数为奇数的顶点，则任意顶点都可以作为起点。如果让我们判定图6.2是否有一条经过所有的结点一次，且仅一次的回路（哈密顿回路），则是一个比较困难的问题。目前还没有找到一个多项式时间算法，也许是科学家尚未找到，也许可能是本质上就不存在这样的有效算法。但如果给定了一个任意的回路，我们能很容易判断它是否是哈密顿回路，只要判断是不是所有的顶点都在回路中就可以了。对于一个判定问题，验证实例的答案为“是”的计算时间为多项式时间的问题，则称判定问题是非多项式确定的，简称NP类问题。显然NPP，但P=NP是否成立呢？这是一个至今还没有解决重要的难题，是当今数学与计算机科学的主攻问题之一，它十分困难，又非常重要，是计算机数学的心腹之患。