分治技术课件

分治技术

3.1分治策略的思想

3.2大整数乘法

3.3矩阵相乘的Strassen算法

3.4选择（Selection）问题的线性算法

13.1分治策略的思想分治算法把一个规模为n的问题实例划分为若干个规模较小的子问题：其规模分别为然后递归地解这k个子问题，最后把k个子结果合并为整个问题的解。分治算法的几个要点是：递归基础：为了保证递归过程在有限步骤内结束，当n值小于某常数n0

时，要有一个简单的处理算法。2划分：分治把长为n的问题实例分成几个部分。许多分治算法简单地取k=2。为了算法有好的性能，划分应该尽量平衡。递归：就是用同样的方法去解各个子问题。如果k个子问题的长度为n1，n2，…，nk

，那么算法执行的总代价和各个子问题的代价应分别为T(n)和T(n1)，T(n2)，..，T(nk)。合并结果：几个子问题获得解决之后，各个结果应合并为整个问题的解。解的合并的代价因情况不同而异。33.2大整数乘法3.2.1选择排序（SelectionSorting）

设Х和Ｙ是两个n位的二进制数，按传统方法计算乘积Х·Ｙ，需要O(n2)次位运算。为简化问题，设n=2k，k为正整数。当n=1时，计算Х·Ｙ就是一次位乘。对Х、Ｙ进行划分：X=A·2n/2+BY=C·2n/2+DA,B,C,D为n/2位的二进制数。ABCDX:Y:4则有：Х·Ｙ=AC·2n+(AD+BC)·2n/2+BD

按上式可以把计算Х·Ｙ的问题划分为四个子问题。即计算n/2位的二进制数的乘积AC，AD，BC，BD。用同样方式计算完成之后，再通过三次n/2位的加法和两次移位，合并为Х·Ｙ。显然，合并代价为O(n)阶。因此得到递归方程如下：

根据主项定理得：（公式3.2）

（公式3.1）

5与我们所期望的不同，简单的分治策略未达到改进的目的。事实上，把一个n位数乘法化为4次n/2位数乘法是不可能改进O(n2)的复杂度的。幸运的是，Х·Ｙ可以有另一计算公式：X·Y=AC·2n+[(A-B)(D-C)+BD+AC]·2n/2+BD公式3.3只有AC、BD和(A-B)(D-C)三次n/2位数的乘法，其合并代价稍有增加，6次加减法、2次移位，仍为O(n)阶。时间复杂度的递归方程为：

（公式3.4）（公式3.3）

6方程的解为：这个算法的设计过程指明：1.

分治策略用于算法设计，往往需要一些技巧。2.

表面上分治只是把一个大问题分成几个子问题，分别计算然后再合并为问题的解，似乎没有明显的节省，但效果却很显著。对于最大元最小元问题，分治策略把计算代价从2n–3减为3n/2–2，大致减少了1/4的工作量；而在n位数乘问题中，代价从O(n2)减少到O(n1.59)，当n较大时，可能会成倍的减速，因为就n0.41这个因子来说，在n=1000时，它大于16。73.3矩阵相乘的Strassen算法

3.3.1问题矩阵运算中，矩阵的元素一般为整型和实型，其基本操作是实数或整数乘法，当数的有效数字位数较多时，数的加法较数的乘法占用时间较少。已知：n阶矩阵A,B，计算乘积C=A·B，计算公式为：其中cij，aij，bij为矩阵C，A，B的元素。显然，完成计算共需n3次乘法和n2(n-1)次加法。（公式3.5）83.3.2分治为了简化问题，设n=2k，k为正整数。直接把矩阵A，B，C一分为四，化为n/2阶矩阵：矩阵乘积C=A·B分解为：（公式3.6）93.6式共需8次n/2阶矩阵相乘和4次n/2阶矩阵相加。显然后者为θ(n2)次数的加法，一般乘法代价高于加法，故也可记为O(n2)次乘法。分治算法的时间代价可由下面的递归方程表示：根据主项定理可知：

遗憾是，简单的分治未能使算法得到改进。（公式3.7）

103.3.3Strassen的分治方法V.Strassen发现公式3.6中的8次矩阵乘法是相关的，他给出了只需7次n/2阶矩阵乘法的算法，付出的代价是原来的4次n/2阶矩阵相加，增加到18次加（减）法运算。从求解3.7式的过程可知，时间代价函数满足：其解为：终于获得了改进。113.3.4Strassen算法的描述算法可以分为下面三步：1.

把n阶矩阵A，B划分为8个n/2阶子矩阵： A11，A12，A21，A22，B11，B12，B21，B22。2.

通过7次n/2阶矩阵相乘，得到n/2阶矩阵M1，M2，..，M7：M1=A11(B12–B22)M2=(A11+A12)B22M3=(A21+A22)B11

M4=A22(B21–B11)M5=(A11+A22)(B11+B22)M6=(A12-A22)(B21+B22)M7=(A11-A21)(B11+B12)12132.

Strassen把8次子矩阵相乘成功地减少为7次。已经证明，采用3.6式的划分方法，至少需要7次乘法，不能再改进了。当然，不同的划分方法，例如把矩阵A，B划分为3×3，5×5个子矩阵，也是可以的。3.

由于矩阵乘法是一个重要的计算问题，许多人努力设计更好的算法。在Strassen之后，O(n2.81)这个时间阶曾多次被改进，分别为：O(n2.795)，O(n2.78)，O(n2.548)，O(n2.494)，目前已知的最好算法达到O(n2.376)。4.算法至今只知道一个平凡的下界Ω(n2)。5.

Strassen算法虽然把时间代价从θ(n3)降至θ(n2.81)阶，但后者的系数要比1大很多。当n比较小（例如n<45）且当矩阵中非零元素较少时，不宜采用此种方法。对于稀疏矩阵的运算，还有其它特殊的有效算法。

143.4选择问题的线性算法3.4.1问题选择问题简单地说就是求n元中的第k元，它与排序问题、比赛问题可以归属于同一类，只是具体要求有区别。它们都是以n个某全序集上的元素作为输入，排序问题是求n个元的全部顺序；比赛问题是只求前k个元的正确顺序；而选择问题是求第k元，对前k–1个元的顺序不关心，对后n–k个元的顺序也不关心，当k=1时即是最小元问题。选择问题的另一个特例是中值问题。3.4.2简单算法解选择问题最简单的解法是直接使用排序算法，对n元L[1..n]进行排序后，取L[k]即为所求。不过最好的排序算法的复杂度为O(nlogn)阶。15从选择问题容易想到快速排序算法中的划分，实际上它是求划分元位于位置k的划分。算法3.1简单的选择算法当取k满足1≤k≤n时，对L[1..n]调用函数QSelect(L,1,n,k)，即可得到所求。这个算法与QuickSort算法十分相近，其区别在于在划分后，只选k所在的一侧进行递归。因此肯定比QuickSort花费的时间代价要小。事实上，平均情形下算法QSelect的时间复杂度为O(n)阶，但在最坏情形下却与快速排序一样是O(n2)阶。3.4.3O(n)阶选择算法的思路1.

虽然采用了分治策略，但上面的算法在最坏情形下的时间复杂度仍然是O(n2)阶的。因为划分算法Partition无法避免划分元位于数组的两端的情况。因此问题的关键是，能否花费O(n)代价改进划分算法，保证每次划分的分点不接近两端。162.

一个较复杂的划分方案：为了实现上述目标，把n元分为个5元组，最后一组可能不足5元，可以用最大数补足。在每个5元组中求中值，得到一个由

中值组成的集合M，然后递归地求出这些中值的中值m*，以这个m*作为划分元。3.

分治：以m*为划分元，把原数组L[1..n]的n个元组成的集合S分为三部分：S1，m*，S2。集合S1中的元素不大于m*，S2中的元素不小于m*。根据k值的大小，决定如何递归。3.4.4算法Select输入：由L[1..n]全部元素组成的集合S和整数k，满足1≤k≤n。设L[1..n]的元素各不相同。输出：S中的第k个最小元。算法3.2Select1718算法Select主要调用三个子函数，第一个是对n≤5时，求第k（≤5）元的算法，因为只调用一次，不必精心设计。5元排序选择算法至多用10次比较就能完成。第二个调用的是Select3in5()，这个函数是在五元中求第三元，在一次递归中需要调用次，因此应设计一个较好的算法。第三个子函数是划分算法MPartition()，显然它的执行依赖于划分元m*的计算过程。实际上在m*的计算过程中，已经确定了肯定小于m*的A组元素和大于m*的D组元素，算法MPartition()只需把B、C组元素与m*比较就可以了。算法的设计并没有对占用空间和元素移动作特殊的要求，因此它可以有多种不同的处理方法。193.4.5算法Select的分析设数组长度n为5的奇数倍，n=5(2r+1)，r为一非负整数，忽略在第2、4步递归调用时数组长度不满足这个假设引起的误差。下面是算法在最坏情形求n元中第k个最小元所需的比较次数。当n≤5时，W(n)≤6，当n=5，k=3时，可至多用6次比较完成。当n>5时，估计1—4步所需的比较次数：1.

求各个5元组的中值，共需6×(n/5)=1.2n次比较；2.

求划分元m*，递归代价为W(n/5)；3.

划分过程中，B、C组元素与m*比较，共4×r≤0.4n次比较；4.

分治操作、递归调用元素个数至多为A、B、C或D、B、C三组元素，总数至多为7n/10，即比较次数不大于W(0.7n)。20综合上述分析，有公式：为了解这个递归不等式，首先估计一个结果，然后用归纳法证明。展开3.9式：（公式3.9）21根据几何级数估计：∴可以估计W(n)≤16n。 （公式3.10）然后用归纳法证明:1°1≤n≤5时，3.10式成立；2°假设，m<n时3.10式成立；3°对m=n（m>5），W(n)≤1.6n+W(0.2n)+W(0.7n)=1.6n+3.2n+11.2n=16n因此，W(n)≤16n确是3.9式的解，算法Select的最坏情形比较次数为O(n)阶，当然其平均情形性能更好。223.4.6讨论1.

线性算法Select的设计过程体现了分治策略用来优化算法设计的威力。设计者除了要掌握划分、递归、平衡和合并等分治的基本要点之外，有时还需要辅以某些特殊的处理，往往能够获得出人意料的成功。2.

改进算法的基本思路是对原有的算法进行分析，在其次要部分付出一定代价，使得算法能在主要部分获得收益。在选择算法的设计过程中：设计一个较好的算法QSelect，它不是一个线性算法。判定算法的递归层数是影响算法时间性能的主要因素，而影响递归层数的主要因素是划分的平衡。在寻找划分元这个环节上，由原来的随机选取改为复杂的方法，付出的代价是第1、2步的1.2n+W(0.2n)。23得到的收益有两点：划分的最坏情形代价由（n-1）减少到0.4n，递归代价由W(n-1)减少为W(0.7n)。事实上，收益大于付出，W(n)由θ(n2)阶降为θ(n)阶。3.

我们给出的“五元组”方法并不是唯一的成功途径。例如V.Rratt，R.Rivest和R.Taijan设计的选择算法的最坏情形比较次数达到W(n)≤5.43n，目前这方面的最好成果是W(n)≤2.95n。上述的高性能的算法的设计与分析主要具有理论上的价值，在实用中，它们往往有一些缺点，例如算法比较复杂、真正有效的n值比较大等等。4.

选择问题在当k值指定为中值时，称为中值问题。中值问题是求一组数据的中间值，它不同于平均值。24中值问题和选择问题之间有这样的关系：表面上看，时比k取其它值算法应花费更大的代价，但中值问题毕竟是选择问题的一个特例，它应该比选择问题的复杂度更低。不过中值问题复杂度改进的余地已经不大。已有的研究成果指出，对于奇数n，任何基于元素比较的中值算法至少需要1.5n–1.5次比较，进一步的研究指出中值算法的复杂度下界为1.75n–logn，而后又改进为1.8n，目前已知的最好的结果是：对于较大的n，至少需要2n次比较。这个值与最好的选择算法的复杂度W(n)≤2.95n已相差不多。第三章完2526算法3.1简单的选择算法Template<classElement>ElementQselect(Element[]L,intf,intl,intk){if(l==f)returnL[f];

inti=Partition(L,f,l);if(k<i–f+1)QSelect(L,f,i,k);elseQSelect(L,i+1,l,k-i+f-1);}返回27算法3.2Select

Template<classElement>ElementSelect(Element[]L,1,in