第5章〓分治算法 5．1算法思想 许多实用的算法都具有递归的结构： 为解决一个给定的问题，通过递归地调用自己一次或多次来解决与该问题具有相似结构的子问题。分治算法(Divide and Conquer)就是这样一种具有递归结构的算法，其基本思想是把一个问题分解成若干个子问题(这些子问题与原问题在本质上是同一种问题类型，只是问题规模不同)，然后递归地解决子问题，最后把子问题的解组合成原问题的解。递归算法与分治算法情同手足，互不分离，经常同时应用在算法设计之中，并产生许多高效的算法。 分治算法在求解问题时，通常遵循以下3个步骤。 步骤1： 把一个问题分解成若干个子问题。 步骤2： 通过递归地解决子问题来解决原问题。如果子问题的问题规模小到可以用直接的方法求出，那么停止递归。 步骤3： 把这些子问题的解组合成原问题的解。 当一种算法的过程中含有对自身的递归调用时，它的运行时间常用一个递归方程来表示。递归方程描述了求解一个问题规模为n的问题所需要的运行时间可以由其子问题的运行时间来决定。对于递归方程而言，如果知道递归的初始边界，那么能够很方便地利用上一章介绍的方法来求解递归方程。 分治算法的运行时间主要由它的3个步骤决定。令T（n）表示求解一个问题规模为n的问题所需要的运行时间，设问题规模小到可以用直接的方法求解，所花费的时间为Θ（1），即存在一个正整数c，使当n≤c时，问题的求解非常简单，只需要常数级的时间就可以得到该问题的解。假设把问题分解成a个子问题，每个子问题的大小为n/b。值得注意的是，n/b可能是n/b或者「n/b，这里忽略底和顶是因为上一章已经分析； 去掉底和顶，并不影响递归方程的求解。令把问题分解成a个子问题所花费的时间为D（n），每个子问题的解组合起来所花费的时间为C（n），则得到递归方程 T（n）= Θ（1），n≤c aT（n/b）+D（n）+C（n），其他 如果将时间D（n）和C（n）合并成函数f（n），则许多分治算法的时间复杂度可以由上一章介绍的公式法求出。从上面的递归方程可以看出，分治算法的优点是它的运行时间常常可以很容易地由其子问题的运行时间得到。正如上一章所介绍的，分治算法在设计的时候，应尽量减少子问题的个数a或者降低f（n）的数量级，以便设计出更有效的分治算法。 下面介绍分治算法的应用。 5．2合并排序 前面介绍了插入排序算法和选择排序算法，现在利用分治算法的思想，设计一种合并排序算法，其基本步骤如下。 步骤1： 将包含n个元素的序列均分成包含n/2个元素的子序列。 步骤2： 对两个子序列进行递归划分。 步骤3： 把两个已经排序的子序列合并成一个有序序列。 合并排序算法MergeSort(A，p，r)的伪代码如下。 MergeSort(A, p, r) 1if p < r then 2q←(p+r)/2 3MergeSort(A, p, q) 4MergeSort(A, （q+1）, r) 5Merge(A, p, q, r) 在MergeSort(A，p，r)中，要排序的元素保存在数组A中，当前要排序的范围是数组A中位置p~r的元素。当p≥r时，停止递归调用,否则，找出中间划分点q，并分别递归求解两个子问题。两个子问题求解后，它们的解合并在一起，得到原问题的解。求解原问题，只需调用MergeSort(A，1，n)。 合并排序算法的关键步骤是如何把两个有序序列合并成一个有序序列，这个步骤可以用辅助函数Merge(A，p，q，r)来完成，其中，p、q、r是数组下标且p≤q＜r。该函数假设数组A［p..q］和A［（q+1）..r］ 是已排好序的，然后将它们合并为一个有序的子数组A［p..r］。详细的合并过程如下。 Merge(A, p, q, r) 1n1←q-p+1 2n2←r-q 3for i←1 to n1 do 4L［i］←A［p+i-1］ 5for j←1 to n2 do 6R［j］←A［q+j］ 7L［n1+1］←∞ 8R［n2+1］←∞ 9i←1 10j←1 11for k ← p to r do 12if L［i］≤R［j］ then 13A［k］←L［i］ 14i←i+1 15else 16A［k］←R［j］ 17j←j + 1 Merge(A，p，q，r)用两个子数组L［1..（n1+1）］，R［1..（n2+1）］分别保存两个已经排好序的序列，以便腾出数组A中的位置来保存合并后的元素。同时，两个数组均多开辟一个存储单元来存储一个非常大的整数∞，其好处是方便元素比较。由于数组L和R的元素均有序且按从小到大已完成排列，因此，只需依次比较两个数组中最前面的两个元素L［i］和R［j］，将较小的元素存储在A数组中。然后重复上述过程，直至两个数组为空。合并排序算法的过程如图5.1所示，其中，实线箭头指向逐步划分的过程，虚线箭头指向逐步合并的过程。 图5．1合并排序算法的过程 由于合并排序算法的正确性主要取决于合并算法，如果能证明合并算法的正确性，则合并排序算法的正确性就不难证得。下面证明合并算法的正确性。 考虑合并算法的循环不变量： 在for循环执行第k次迭代前，子数组A［p..（k-1）］有序地存放了L［1..（n1+1）］和R［1..（n2+1）］中较小的k-p个元素，L［i］和R［j］是各自数组中还未复制到数组A的最小的元素。那么要证明的是： 执行for循环的第k次迭代后，循环不变量依然为真。同样地，这个循环不变量在算法结束时依然为真，从而可以证明算法的正确性。具体步骤如下。 （1） 初始步： 在for循环执行k=p之前，子数组A［p..（p-1）］不存在元素，是个空数组。这个空数组包含了k-p=0个L和R的最小元素； 同时，i=j=1，L［1］和R［1］即为还未复制到数组A的两个数组中各自最小的元素，因此循环不变量为真。 （2） 归纳步： 假设在执行for循环第k次迭代前，循环不变量为真。为了能清楚地了解每次迭代中循环不变量是否为真，不妨假设L［i］≤R［j］。此时L［i］是还未复制到数组A的最小元素。因为假设A［p..（k-1）］有序地存放了L［1..（n1+1）］和R［1..（n2+1）］中最小的k-p个元素，执行for循环的第k次迭代后，在行13把L［i］复制到A［k］后，数组A［p..k］将包含k-p+1个最小元素。整数k(在for循环中增加)和i(代码行14)在每次迭代后都发生改变，因而代码行13、行14的执行使得循环不变量为真，即在执行for循环第k+1次迭代前，循环不变量为真。 （3） 终止步： 程序结束时k=r+1，子数组A［p..（k-1）］也就是A［p..r］有序地包含了k-p=r-p+1个L［1..（n1+1）］和R［1..（n2+1）］中最小的元素。数组L和R总共包含了n1+n2+2=r-p+3个元素。此时，除了两个最大的元素没有合并到数组A外，L和R的其他元素都已经有序地合并到A了，因此循环不变量为真，合并算法正确地把两个有序数组合并成一个有序数组。 在合并排序算法中，令T（n）表示对元素个数为n的数组进行排序所需要的时间，对数组均匀划分后，可得到两个规模均为n/2的子问题。合并排序算法对这两个子问题的解进行合并，最多需要时间Θ（n）。综上所述，合并排序算法所需要的时间为 T（n）=2T（n/2）+Θ（n） 利用前面介绍的公式法，可得合并排序算法的时间复杂度为T（n）=O（nlgn）。由于排序问题的下界为Ω（nlgn），因此，合并排序算法是渐近最有效的算法，对解决问题规模大的问题比较有效。 5．3快速排序 前面介绍了排序问题可以用分治算法来求解，下面设计另一种分治算法——快速排序算法，来求解排序问题。快速排序算法是一种非常有创意的算法，对问题规模比较大的排序问题非常有效，因而被誉为20世纪最好的10种算法之一。霍尔（C．A.R．Hoare）就因其代表性贡献——快速排序算法，而获得1980年的图灵奖。 快速排序算法采用分治算法的思想。令对n个元素排序的问题用数组A［1..n］表示，考虑一般问题A［p..r］的分治求解过程，具体如下。 （1） 把问题A［p..r］分解成两个子问题A［p..（q-1）］和A［（q+1）..r］，并且满足A［p..（q-1）］的元素都小于或等于A［q］，A［（p+1）..r］的元素都比A［q］大，其中，A［q］称为支点。计算索引q的过程就是划分子问题的过程。 （2） 对A［p..（q-1）］和A［（q+1）..r］这两个子问题分别进行递归求解。 当每个子问题都得到解决，数组也就排好序了。这时，每个元素在正确位置，因而也就没有必要把子问题的解组合在一起了，即分治算法的第三步对于快速排序算法来说，没有必要执行。下面给出快速排序算法QuickSort(A，p，r)的伪代码。 QuickSort(A,p,r) 1if p < r then 2q←Partition(A, p, r) 3QuickSort(A, p, q-1) 4QuickSort(A, q+1, r) 要解决原问题，只需要调用QuickSort(A，1， n)。 QuickSort(A，p，r)的过程非常简单，但其中的Partition(A，p，r)过程非常关键。下面来分析该过程。由于在分治算法划分的过程中，需要确定一个支点，这里简单地取A［r］为支点。为了将比支点大的元素及比支点小或相等的元素分离，需要对数组进行扫描，即将数组中的元素逐一与A［r］进行比较。同时，引入两个变量i和j，标记两个子问题A［p..i］和A［（i+1）..j］的大小。具体地，Partition(A，p，r)过程可以描述如下。 Partition(A, p, r) 1x←A［r］ 2i←p-1 3for j←p to r-1 do 4if A［j］≤x then 5i←i+1 6A［i］  A［j］ 7A［i+1］  A［r］ 8return i+1 下面给出一个例子，分析快速排序算法的运行过程。 图5．2给出了一般问题A［p..r］的划分过程。图5．2(a)给出了执行扫描前的状态，A［r］=4为支点，将A［j］=2与A［r］进行比较，可得A［j］＜A［r］，因而i往前移动一格。此时i=j，A［j］跟自己交换，得到图5．2(b)。此时A［j］=8与A［r］比较，A［j］＞A［r］，因此不改变，j往前移动一格，得到图5．2(c)。重复上述过程，最终得到两个子问题A［p..（q-1）］和A［（q+1）..r］。 图5．2快速排序算法的运行过程 下面给出快速排序的运行时间复杂度分析。 对快速排序算法来说，最坏的情形发生在Partition(A，p，r)过程所产生的两个子数组中，即一个子数组有n-1个元素而另一个有0个，有 T（n）=T（n-1）+O（n） 利用递归树方法展开上式，可以得到 T（n）=T（n-1）+O（n） =T（n-2）+O（n）+O（n-1） =…=O（n2） 这样可以估计出快速排序算法的最坏情形时间复杂度为O（n2）。然后可以利用替换方法加以证明，读者可以自己证明。 快速排序算法最好情形发生在“二等分”的时候，即Partition(A，p，r)生成的两个子问题，一个子问题的问题规模为n/2，另一个子问题的问题规模为「n/2-1。在这种情况下，快速排序算法的速度是最快的。忽略底和顶，快速排序算法的运行时间表达式为 T（n）=2T（n/2）+Θ（n） 利用第4章介绍的公式法，可以得到快速排序算法最好情形的时间复杂度为T（n）=Ω（nlgn）。 下面介绍快速排序算法平均情形时间复杂度的分析。由于快速排序算法只与要排序的序列值的相对顺序有关，与具体的值无关,因此，不妨假设要排序的序列的元素值是各不相同的。为了进一步简化分析，假设序列的每种排列作为算法的输入机会是均等的。把输入序列看成是随机的，这保证了数组的每个元素被选为支点的概率是相等的，即为1/n。假设排序为q的元素被选择为支点，则原问题可以分解成两个子问题，一个问题规模为q-1，另一个问题规模为n-q。设T（n）表示对一个元素数为n的数组A进行快速排序的平均运行时间，则有 T（n）=∑nq=11n（T（q-1）+T（n-q）+n-1）=1n∑nq=1（T（q-1）+T（n-q））+n-1 由于∑nq=1T（q-1）=∑nq=1T（n-q），则有 T（n）=1n∑nq=1（T（q-1）+T（n-q））+n-1 =2n∑nq=1T（q-1）+n-1 即 nT（n）=2∑nq=1T（q-1）+n（n-1）(5．1) 类似地有 （n-1）T（n-1）=2∑n-1q=1T（q-1）+（n-1）（n-2）(5．2) 式(5．1)和式(5．2)相减，可得 nT（n）-（n-1）T（n-1）=2T（n-1）+2（n-1） 整理可得nT（n）=（n+1）T（n-1）+2（n-1），两边同时除以n（n+1），可得 T（n）n+1=T（n-1）n+2（n-1）n（n+1） 令D（n）=T（n）n+1，得 D（n）=0，n=1 D（n-1）+2（n-1）n（n+1），n＞1 利用递归树的方法，可以得 D（n）=2∑nj=1（j-1）j（j+1）=Θ（lgn） 故快速排序算法的平均时间复杂度为 T（n）=（n+1）Θ（lgn）=Θ（nlgn） 快速排序算法虽然不是渐近最有效的算法，但是当求解问题规模比较大的问题时，效果并不会比合并排序算法差。如果利用随机选择支点的策略，则快速排序算法的效率会更高。 5．4大整数乘法 设u和v表示两个n位大整数，大整数乘法问题是计算u×v的值。当两个整数的位数比较小时，这个问题很简单； 当n非常大时，这个问题就变得非常复杂。按照通常的乘法运算，大整数乘法需要Θ（n2）次位运算，如图5．3所示。在密码系统与信息安全、数字信息、加密解密等领域，经常遇到大整数乘法问题，因此，寻找更快的求解算法变得尤为重要。下面介绍求解大整数乘法的分治算法。 假设大整数u和v分别表示为n位二进制形式，每个大整数可分解为高位和低位两部分，每部分为n/2位。假设大整数u分成w和x两部分，大整数v分成y和z两部分，如图5．4所示。 图5．3乘法的图形表示 图5．4大整数u和v的划分 因此，大整数u和v可以分别表示为 u=w2n/2+x，v=y2n/2+z 则 uv=（w2n/2+x）（y2n/2+z）=wy2n+（wz+xy）2n/2+xz 这样原问题可以转化为位数更少的两个整数相乘的问题。值得注意的是，乘以2n表示向左移动n位，这个运算耗时Θ（n）。 令T（n）表示两个n位整数相乘所需要的计算时间，要计算uv，需要4次两个整数的乘法及3次加法运算，其中，后者耗时Θ（n），即可计算出T（n）为 T（n）=Θ（1），n=1 4T（n/2）+Θ（n），n＞1 利用公式法可知，T（n）=O（n2）。 从时间复杂度来看，这种求解大整数的分治算法比通常的乘法运算没有什么优势。如果能减少子问题的个数a(这里a=4)，则可以提高算法的效率。事实上，如果利用恒等式： wz+xy=（w+x）（y+z）-wy-xz，则可以得到算法Multiply2Int(u，v)，其伪代码如下。 Multiply2Int(u, v) 1if |u| = |v| = 1 then return uv 2else 3A1← Multiply2Int(w, y) 4A2 ← Multiply2Int(x, z) 5A3← Multiply2Int(w+x, y+z) 6return A12n+（A3-A1-A2）2n/2+A2 其中，|u|表示u的位数。Multiply2Int(u，v)虽然增加了加法运算的次数，但是加法运算的耗时不多，而且减少了乘法运算的次数，只需要3次乘法运算，即只需求解3个子问题，因此其时间复杂度可用递归方程表示为 T（n）=Θ（1），n=1 3T（n/2）+Θ（n），n＞1 利用公式法得到T（n）=O（nlg3）=O（n1.59）。由此可见，减少子问题两个数可得到具有更低时间复杂度的算法。 5．5矩阵乘法 给定两个n×n阶矩阵A和B，问题是要求它们的乘积，即计算C=A×B。令A=（aik），B=(bkj),C=(cij),对于这个问题，可以用下式来计算，即 cij=∑nk=1aikbkj 一般地，计算n×m矩阵A和p×q矩阵B乘积的算法，可以描述如下。 MatrixMultiply(A, B) 1if m≠p then 2print "Two matrices cannot multiply" 3else 4for i←1 to n do 5for j←1 to q do 6cij ←0 7for k←1 to m do 8cij ←cij + aik×bkj 9return C MatrixMultiply(A，B)算法的运行时间复杂度为O（nmq）。是否可以得到更有效的算法呢？现在考虑计算两个n×n阶矩阵乘积，并且假设n=2k（k≥0）。如果n≥2，那么A、B，可以被分成4个n2×n2阶矩阵，分别为 A=A11A12 A21A22， B=B11B12 B21B22， C=C11C12 C21C22 利用块矩阵的乘积，矩阵C可以表示为 C=A11B11+A12B21A11B12+A12B22 A21B11+A22B21A21B12+A22B22 由上式可知，原问题的求解可以转化为8个子问题的求解，子问题中的矩阵规模是n2×n2。子问题求解完成后，仍然是一个n2×n2阶矩阵。子问题求解完成后，还包括4个n2×n2阶矩阵相加，因此原问题的计算量为 T（n）=Θ（1），n=1 8T（n/2）+Θ（n2），n＞1 利用公式法，可以知道上述算法的时间复杂度为O（n3），这跟两个矩阵直接相乘的计算量没有什么差别。是否可以计算得更快呢？Strassen通过仔细地研究发现，可以牺牲加、减运算的开销来减少乘法的次数，并提出了Strassen算法，其思路如下： 要计算矩阵乘积 C=A11A12 A21A22 B11B12 B21B22 只需要计算 C= d1+d4-d5+d7d3+d5 d2+d4d1+d3-d2+d6 其中 d1=（A11+A22）（B11+B22） d2=（A21+A22）B11 d3=A11(B12-B22) d4=A22(B21-B11) d5=（A11+A12）B22 d6=（A21-A11）（B11+B12） d7=（A12-A22）（B21+B22） 由上可知，两个n×n阶矩阵相乘的计算量是两个(n/2)×(n/2)阶矩阵相乘计算量的7倍，加上它们进行加或减运算的18倍，加减运算共需要Θ（n2），因此有 T（n）=Θ（1），n=1 7T（n/2）+Θ（n2），n＞1 根据Strassen算法，两个n×n阶矩阵相乘原来需要求解8个子问题，现在只需要求解7个子问题，当然这带来加减法运算量的增加。根据公式法，可得上述递归方程的解为T（n）=O（nlg7）=O（n2.81），因而Strassen算法的效率更高。虽然Strassen算法的渐近效率很高，但是这类漂亮的算法因常数系数很大而缺乏应用价值，因此对于小规模问题计算矩阵相乘常用的还是矩阵直接相乘的算法。 视频讲解 5．6残缺棋盘游戏 残缺的棋盘表示棋盘中有一个格子残缺，图5．5(a)所示为一个4×4的残缺棋盘，其中，黑格表示残缺格。给定一个能覆盖3个格子的L形三格板，其中，三格板有4个放置方向，如图5．5(b)所示。 图5．5一个4×4的残缺棋盘 残缺棋盘游戏问题是给定一个2n×2n的残缺棋盘，求解三格盘的放置方法，使除了残缺格外，棋盘中其他格子可被三格板覆盖，并满足放置的三格板互不重叠。现在可以很容易地计算出： 对于一个2n×2n的残缺棋盘，除了残缺格外，共需要放置（2n×（2n-1））/3个三格板。图5．6展示了2n×2n的残缺棋盘的三格板铺满过程，可知共需要5个三格板。 从图5．7可以看出，放置一个三格板后，棋盘中间区域已经铺满。如果把这个三格板看成3个残缺格，那么原来的残缺棋盘可以分解为4个残缺棋盘。虽然这4个残缺棋盘中有3个与原来的残缺棋盘不相似，但是通过放置一个三格板，并把三格板所在的格子看作残缺格，这样可以将原来不相似的3个棋盘构造成残缺棋盘，这3个棋盘的放置方法可以采用类似原来残缺棋盘的放置方法进行求解。当残缺棋盘的规模为2×2时，棋盘不再分解，递归终止，这是因为残缺棋盘此时只要放置一个三格板就可以被铺满。 从上述例子中可以得到启示，残缺棋盘游戏的问题可以利用分治算法求解。要完成残缺棋盘游戏，必须定位棋盘和残缺格的位置。当棋盘被一分为四，确定残缺格的位置后，便可以知道该对哪3个棋盘补残缺格。例如，对于图5．7而言，确定残缺格的位置后可知，左上棋盘的右下角为残缺格，左下棋盘的右上角为残缺格，右上棋盘的左下角为残缺格。 图5．6一个残缺棋盘的铺满过程 图5．7残缺棋盘的划分 令二维整数数组Board表示棋盘，其中，Board［0，0］表示棋盘左下角的方格； t记录放置的三格板的数目； tr表示残缺棋盘左下角方格所在行； tc表示棋盘左下角方格所在列； dr表示残缺格所在行； dc表示残缺格所在列； size表示棋盘的行数或列数，则利用分治算法求解残缺棋盘游戏问题的伪代码可以描述为TileBoard(tr，tc，dr，dc，size)，具体如下。 TileBoard(tr, tc, dr, dc, size) 1if size = 1 return ok 2tile←tile+1; t←tile 3s←size/2 4if dr < tr + s and dc < tc + s then 5TileBoard(tr, tc, dr, dc, s) 6else 7Board［tr + s-1, tc + s - 1］←t 8TileBoard(tr, tc, tr+s-1, tc+s-1, s) 9if dr < tr + s and dc ≥ tc + s then 10TileBoard(tr, tc+s, dr, dc, s) 11else 12Board［tr + s-1, tc + s］←t 13TileBoard(tr, tc+s, tr+s-1, tc+s, s) 14if dr≥ tr + s and dc < tc + s then 15TileBoard(tr+s, tc, dr, dc, s) 16else 17Board［tr + s, tc + s -1］←t 18TileBoard(tr+s, tc, tr+s, tc+s-1, s) 19if dr ≥ tr + s and dc ≥ tc + s then 20TileBoard(tr+s, tc+s, dr, dc, s) 21else 22Board［tr + s, tc + s］←t 23TileBoard(tr+s, tc+s, tr+s, tc+s, s) 其中行1表示： 如果棋盘大小为21×21，则算法结束，否则，将棋盘划分为4个小棋盘。然后，根据残缺格所在的位置，递归调用4次，以解决4个子问题。其中，在算法实现时，tile是全局变量，初始为0。 下面分析TileBoard(tr，tc，dr，dc，size)的时间复杂度。 令T（n）表示完成一个规模为2n×2n的残缺棋盘游戏所花费的时间，当棋盘规模为2×2时，残缺棋盘游戏显然可以在常数时间Θ（1）内完成。因此，T（n）的递归方程为 T（n）=Θ（1），n=1 4T（n-2）+Θ（1），n＞1 利用递归树的方法将其展开，可得 T（n）=4T（n-1）+Θ（1） =4［4T（n-2）+Θ（1）］+Θ（1） =42T（n-2）+4Θ（1）+Θ（1） =43T（n-3）+42Θ（1）+4Θ（1）+Θ（1）  =4n-1T（1）+4n-2Θ（1）+…+4Θ（1）+Θ（1） =Θ（4n-1） 上述例子表明，分治算法通过把问题分解为较小的子问题来解决原问题，简化或减少了求解原问题的计算量。 5．7快速傅里叶变换 快速傅里叶变换(Fast Fourier Transform，FFT)，是求解离散傅里叶变换（Discrete Fourier Fransform，DFT）的快速算法，在数字信号处理、图像处理、计算大整数乘法、求解偏微分方程等问题上具有广泛的应用。FFT的影响是如此巨大，以至于它被誉为20世纪最好的算法之一。 DFT的计算公式为 bj=∑n-1k=0akωkj，j=0，1，…，n-1 其中，ω=e2πi/n为n次单位元根，i=-1； A=〈a0，a1，…，an-1〉为已知。 DFT逆变换为 ak=1n∑n-1j=0bjω-jk，k=0，1，…，n-1 如果DFT的快速求解算法找到了，那么其逆变换同样可以快速求得。DFT与多项式的计算关系紧密，事实上，考虑多项式p（x） p（x）=a0+a1x+a2x2+…+an-1xn-1 则DFT的bj是p（x）在x=ωj处的值。前面介绍过Horner法则，计算p（x）在某点的值，其时间复杂度为O（n），因此计算bj（j=0，1，…，n-1）的时间复杂度为O（n2），而利用FFT，其时间复杂度仅为O（nlgn）。下面介绍FFT。 将多项式p（x）分解为奇次幂部分和偶次幂部分，为 p（x）=（a1x+a3x3+…+an-1xn-1）+（a0+a2x2+…+an-2xn-2） =（a1+a3x2+…+an-1xn-2）x+（a0+a2x2+…+an-2xn-2） 令y=x2，则有 p（x）=（a1+a3y+…+an-1yn2-1）x+（a0+a2y+…+an-2yn2-1） =q（y）x+r（y） 因此p（x）在x=ωjj=0，1，…，n2-1处的值可表示为 p（ωj）=q（ω2j）ωj+r（ω2j） 根据复数的性质ωj+n2=-ωj，有 pωj+n2=-q（ω2j）ωj+r（ω2j） 上述推导过程说明： 求解次数为n的多项式p（x）在x=ωj处的值，可以转化为求两个次数为n/2的多项式q（x）和r（x）在x=（ω2）j处的值的问题。如果n是2的幂，则可以利用分治算法继续分解，直到p（x）是常数为止。下面给出算法 RecursiveFFT（A，ω）的伪代码，具体如下。 RecursiveFFT(A, ω) 1if n=1 then return A 2x←ω0 3A2←〈a0，a2，…，an-2〉 4A1←〈a1，a3，…，an-1〉 5q←RecursiveFFT(A2，ω2) 6r←RecursiveFFT(A1，ω2) 7for k←0 to （n/2）-1 do 8bk←x×r+q 9bk+n2←-x×r+q 10x←xω 11return b 其中，b=〈b0，b1，…，bn-1〉即为所求。令T（n）表示计算b需要的时间，则有 T（n）=2T（n/2）+O（n） 利用公式法可得T（n）=O（nlgn）。 DFT与其逆变换有相同的形式，因此FFT也可以用来计算DFT的逆变换。此外，利用FFT还可以在O（nlgn）时间内计算两个多项式的乘积。值得注意的是，FFT需要考虑多项式p（x）在一些特殊点x=ωj（j=0，1，…，n-1）处的计算。 5．8小结 本章内容主要参考文献［2，5，7］，介绍了分治算法的设计及其时间复杂度的分析，以及分治算法的应用。提高分治算法的效率是算法设计的关键，对此，一种方法是减少子问题的个数来提高分治法的效率，另一种方法是减少划分问题及合并子问题解的计算量。当然，这里面也有一对矛盾的关系，即减少子问题的个数，可能会增加划分问题及合并子问题解的计算量，这就需要根据具体问题来平衡考虑。还有一种方法是，避免公共子问题的重复计算，这也是第6章动态规划算法里要考虑的问题。分治算法是算法领域最基本的技术。虽然分治算法有时求解问题的效率不太高，但是许多有效的算法都是基于分治的思想。 习题 51将合并排序算法改写成迭代算法(非递归算法)，尽可能地使算法更有效。 52给出算法Strassen计算下列矩阵乘积的过程。 31 4-1 2-5 6-3 53给定一个有序数组A［1..n］，以及一个元素x，设计一种寻找x的分治算法，并分析其时间复杂度，同时要求返回x在数组中的位置。 54设计一种求n个元素中最小值和最大值的迭代算法，要求仅比较3n/2-2次，其中，n表示2的幂。 55设计一种求n个整数数组A［1..n］所有元素和的分治算法。求解思路： 将输入元素近似地划分成两半入手。 56给定n个整数的数组A［1..n］，以及一个整数x，设计一种分治算法，求出x在数组A中出现的次数，并分析所设计算法的时间复杂度。 57给出一个由n个元素组成的数组A［1..n］，以及两个元素x1和x2，设计一种寻找两个元素位置的分治算法。 58按照下述思路修改算法MergeSort： 首先把输入数组A［p..r］划分成4个部分A1、A2、A3和A4，并取代原来的两部分； 然后分别对每部分进行递归排序； 最后将4个已排序部分合并，得到一个有序的数组。为了简单起见，假设n是4的幂。请设计修改算法并分析其时间复杂度。 59给定n个互不相同元素的数组A［1..n］，要求设计找出数组中第k小元素的分治算法，并分析其时间复杂度。 510修改算法QuickSort，使它能够求解选择问题(习题59)，并分析修改后算法的最坏情形及平均情形时间复杂度。 511将算法QuickSort转化为迭代算法。 512考虑在具有n个互不相同元素的数组A［1..n］中找出前k个最小元素的问题，其中，k不是常量，而是输入数据的一部分。可以用排序算法解此问题并返回A［1..k］，然而耗费的时间为O（nlgn），试设计一种时间复杂度为Θ（n）的算法。 513设x=a+bi和y=c+di是两个复数。只要4次乘法就可以很容易地计算乘积xy，也就是xy=(ac－bd)+(ad+bc)i。设计一种算法，只用3次乘法就可以计算出xy。 514已知序列A=〈a0，a1，a2，a3〉，给出算法RecursiveFFT的计算过程及结果。 515设计一种分治算法，使之能判断两个二叉树T1和T2是否相同。 516设计一种分治算法，使之能计算一棵二叉树的高度。 517设计一种分治算法，在一个具有n个数的数组中找出第二大的元素，并分析算法的时间复杂度。 518说明如何用三格板来平铺没有方格缺失的2i×3j平板，其中，i和j都是正整数。 实验题 519编写程序实现残缺棋盘游戏算法，并用图形演示。 520分别将插入排序、选择排序、合并排序和快速排序算法进行编程实现，并使用实验分析法比较这些算法的效率。 521继续改进石材切割问题。