Algorithm 版 (精华区)

发信人: Lerry (第一次有失恋的感觉), 信区: Algorithm
标  题: 分治法的实例分析
发信站: 哈工大紫丁香 (2002年03月12日11:09:56 星期二), 站内信件

分治法的实例分析
以上讨论的是分治法的基本思想和一般原则，下面我们用具体的例子来说明如何针对具
体问题用分治法来设计有效解法。
例1和例2是分治法的经典范例，其分解和合并过程都比较简单明显；例3和例4的合并方
法有多种选择，只有选择最好的合并方法才能够改进算法的复杂度；例5是一个计算几何
学中的问题，它的合并步骤需要较高的技巧。例6则是IOI'95的试题 Wires and Switch
es 。
例1 二分查找
例2 快速排序
例3 大整数乘法
例4 Strassen矩阵乘法
例5 最接近点对问题
例6 导线和开关
更多实例请参阅分治法问题集

二分查找法 Binary Search
在对线性表的操作中，经常需要查找某一个元素在线性表中的位置。此问题的输入是待
查元素x和线性表L，输出为x在L中的位置或者x不在L中的信息。
比较自然的想法是一个一个地扫描L的所有元素，直到找到x为止。这种方法对于有n个元
素的线性表在最坏情况下需要n次比较。一般来说，如果没有其他的附加信息，在有n个
元素的线性表中查找一个元素在最坏情况下都需要n次比较。
下面我们考虑一种简单的情况。假设该线性表已经排好序了，不妨设它按照主键的递增
顺序排列（即由小到大排列）。在这种情况下，我们是否有改进查找效率的可能呢？
如果线性表里只有一个元素，则只要比较这个元素和x就可以确定x是否在线性表中。因
此这个问题满足分治法的第一个适用条件；同时我们注意到对于排好序的线性表L有以下
性质：
比较x和L中任意一个元素L[i]，若x=L[i]，则x在L中的位置就是i；如果x<L[i]，由于L
是递增排序的，因此假如x在L中的话，x必然排在L[i]的前面，所以我们只要在L[i]的前
面查找x即可；如果x>L[i]，同理我们只要在L[i]的后面查找x即可。无论是在L[i]的前
面还是后面查找x，其方法都和在L中查找x一样，只不过是线性表的规模缩小了。这就说
明了此问题满足分治法的第二个和第三个适用条件。很显然此问题分解出的子问题相互
独立，即在L[i]的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件
。
于是我们得到利用分治法在有序表中查找元素的算法。
function Binary_Search(L,a,b,x);
begin
  if a>b then return(-1)
            else begin
                   m:=(a+b) div 2;
                   if x=L[m] then return(m)
                             else if x>L[m]
                                    then return(Binary_Search(L,m+1,b,x));
                                    else return(Binary_Search(L,a,m-1,x));
                  end;
end;
在以上算法中，L为排好序的线性表，x为需要查找的元素，b,a分别为x的位置的上下界
，即如果x在L中，则x在L[a..b]中。每次我们用L中间的元素L[m]与x比较，从而确定x的
位置范围。然后递归地缩小x的范围，直到找到x。
下面分析该算法的复杂性。设在n个元素的数组中查找x需要的比较次数为T(n)，如果每
次比较x和L[m]时，总有x<>L[m]，即x根本不在L中，则：
T(n)=2+T(n/2),T(1)=1
该方程的解为T(n)=O(logn)。所以在最坏情况下二分查找法的复杂度为O(logn)。

快速排序 Quick Sort
我们已经知道，在决策树计算模型下，任何一个基于比较来确定两个元素相对位置的排
序算法需要Ω(nlogn)计算时间。如果我们能设计一个需要O(n1ogn)时间的排序算法，则
在渐近的意义上，这个排序算法就是最优的。许多排序算法都是追求这个目标。
下面介绍快速排序算法，它在平均情况下需要O(nlogn)时间。这个算法是由C.A.R.Hoar
e发明的。
算法的基本思想
快速排序的基本思想是基于分治策略的。对于输入的子序列L[p..r]，如果规模足够小则
直接进行排序，否则分三步处理：
分解(Divide)：将输入的序列L[p..r]划分成两个非空子序列L[p..q]和L[q+1..r]，使L
[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。
递归求解(Conquer)：通过递归调用快速排序算法分别对L[p..q]和L[q+1..r]进行排序。

合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在L[p..q]和L[q+
1..r]都排好序后不需要执行任何计算L[p..r]就已排好序。
这个解决流程是符合分治法的基本步骤的。因此，快速排序法是分治法的经典应用实例
之一。
算法的实现
算法Quick_Sort的实现：
注意：下面的记号L[p..r]代表线性表L从位置p到位置r的元素的集合，但是L并不一定要
用数组来实现，可以是用任何一种实现方法（比如说链表），这里L[p..r]只是一种记号
。
procedure Quick_Sort(p,r:position;var L:List);
const
e=12;
var
q:position;
begin
1  if r-p<=e then Insertion_Sort(L,p,r)//若L[p..r]足够小则直接对L[p..r]进行插
入排序
     else begin
2            q:=partition(p,r,L);//将L[p..r]分解为L[p..q]和L[q+1..r]两部分
3            Quick_Sort(p,q,L);  //递归排序L[p..q]
4            Quick_Sort(q+1,r,L);//递归排序L[q+1..r]        
          end;
end;
对线性表L[1..n]进行排序，只要调用Quick_Sort(1,n,L)就可以了。算法首先判断L[p.
.r]是否足够小，若足够小则直接对L[p..r]进行排序，Sort可以是任何一种简单的排序
法，一般用插入排序。这是因为，对于较小的表，快速排序中划分和递归的开销使得该
算法的效率还不如其它的直接排序法好。至于规模多小才算足够小，并没有一定的标准
，因为这跟生成的代码和执行代码的计算机有关，可以采取试验的方法确定这个规模阈
值。经验表明，在大多数计算机上，取这个阈值为12较好，也就是说，当r-p<=e=12即L
[p..r]的规模不大于12时，直接采用插入排序法对L[p..r]进行排序(参见 Sorting and
 Searching Algorithms: A Cookbook)。当然，比较方便的方法是取该阈值为1，当待排
序的表只有一个元素时，根本不用排序(其实还剩两个元素时就已经在Partition函数中
排好序了)，只要把第1行的if语句该为if p=r then exit else ...。这就是通常教科书
上看到的快速排序的形式。
注意：算法Quick_Sort中变量q的值一定不能等于r，否则该过程会无限递归下去，永远
不能结束。因此下文中在partition函数里加了限制条件，避免q=r情况的出现。
算法Quick_Sort中调用了一个函数partition，该函数主要实现以下两个功能：
在L[p..r]中选择一个支点元素pivot;
对L[p..r]中的元素进行整理，使得L[p..q]分为两部分L[p..q]和L[q+1..r]，并且L[p.
.q]中的每一个元素的值不大于pivot，L[q+1..r]中的每一个元素的值不小于pivot，但
是L[p..q]和L[q+1..r]中的元素并不要求排好序。
快速排序法改进性能的关键就在于上述的第二个功能，因为该功能并不要求L[p..q]和L
[q+1..r]中的元素排好序。
函数partition可以实现如下。以下的实现方法是原地置换的，当然也有不是原地置换的
方法，实现起来较为简单，这里就不介绍了。
function partition(p,r:position;var L:List):position;
var
pivot:ElementType;
i,j:position;
begin
1  pivot:=Select_Pivot(p,r,L); //在L[p..r]中选择一个支点元素pivot
2  i:=p-1;
3  j:=r+1;
4  while true do
     begin
5      repeat j:=j-1 until L[j]<=pivot;  //移动左指针，注意这里不能用while循
环
6      repeat i:=i+1 until L[i]>=pivot;  //移动右指针，注意这里不能用while循
环
7      if i< j then swap(L[i],L[j])  //交换L[i]和L[j]
8              else if j<>r then return j        //返回j的值作为分割点
9                           else return j-1;     //返回j前一个位置作为分割点

     end;
end;
该算法的实现很精巧。其中，有一些细节需要注意。例如，算法中的位置i和j不会超出
A[p..r]的位置界，并且该算法的循环不会出现死循环，如果将两个repeat语句换为whi
le则要注意当L[i]=L[j]=pivot且i<j时i和j的值都不再变化，会出现死循环。
另外，最后一个if..then..语句很重要，因为如果pivot取的不好，使得Partition结束
时j正好等于r，则如前所述，算法Quick_Sort会无限递归下去；因此必须判断j是否等于
r，若j=r则返回j的前驱。
以上算法的一个执行实例如图1所示，其中pivot=L[p]=5：
图1 Partition过程的一个执行实例
Partition对L[p..r]进行划分时，以pivot作为划分的基准，然后分别从左、右两端开始
，扩展两个区域L[p..i]和L[j..r]，使得L[p..i]中元素的值小于或等于pivot，而L[j.
.r]中元素的值大于或等于pivot。初始时i=p-1，且j=i+1，从而这两个区域是空的。在
while循环体中，位置j逐渐减小，i逐渐增大，直到L[i]≥pivot≥L[j]。如果这两个不
等式是严格的，则L[i]不会是左边区域的元素，而L[j]不会是右边区域的元素。此时若
i在j之前，就应该交换L[i]与L[j]的位置，扩展左右两个区域。 while循环重复至i不再
j之前时结束。这时L[p..r]己被划分成L[p..q]和L[q+1..r]，且满足L[p..q]中元素的值
不大于L[q+1..r]中元素的值。在过程Partition结束时返回划分点q。
寻找支点元素select_pivot有多种实现方法，不同的实现方法会导致快速排序的不同性
能。根据分治法平衡子问题的思想，我们希望支点元素可以使L[p..r]尽量平均地分为两
部分，但实际上这是很难做到的。下面我们给出几种寻找pivot的方法。
选择L[p..r]的第一个元素L[p]的值作为pivot；
选择L[p..r]的最后一个元素L[r]的值作为pivot；
选择L[p..r]中间位置的元素L[m]的值作为pivot；
选择L[p..r]的某一个随机位置上的值L[random(r-p)+p]的值作为pivot；
按照第4种方法随机选择pivot的快速排序法又称为随机化版本的快速排序法，在下面的
复杂性分析中我们将看到该方法具有平均情况下最好的性能，在实际应用中该方法的性
能也是最好的。
下面是一个快速排序的Java Applet演示程序，该程序使用第一种pivot选择法，即选L[
p]为pivot，因此Partition过程作了一些简化，与我们这里的Partition过程实现方法不
同，但功能相同。该程序是针对用数组实现的线性表，用C语言实现的。
　
性能分析
下面我们就最好情况，最坏情况和平均情况对快速排序算法的性能作一点分析。
注意：这里为方便起见，我们假设算法Quick_Sort的范围阈值为1（即一直将线性表分解
到只剩一个元素），这对该算法复杂性的分析没有本质的影响。
我们先分析函数partition的性能，该函数对于确定的输入复杂性是确定的。观察该函数
，我们发现，对于有n个元素的确定输入L[p..r]，该函数运行时间显然为θ(n)。
最坏情况
无论适用哪一种方法来选择pivot，由于我们不知道各个元素间的相对大小关系（若知道
就已经排好序了），所以我们无法确定pivot的选择对划分造成的影响。因此对各种piv
ot选择法而言，最坏情况和最好情况都是相同的。
我们从直觉上可以判断出最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元
素和1个元素的时候(设输入的表有n个元素)。下面我们暂时认为该猜测正确，在后文我
们再详细证明该猜测。
对于有n个元素的表L[p..r]，由于函数Partition的计算时间为θ(n)，所以快速排序在
序坏情况下的复杂性有递归式如下：
T(1)=θ(1), T(n)=T(n-1)+T(1)+θ(n)             (1)
用迭代法可以解出上式的解为T(n)=θ(n2)。
这个最坏情况运行时间与插入排序是一样的。
下面我们来证明这种每次划分过程产生的两个区间分别包含n-1个元素和1个元素的情况
就是最坏情况。
设T(n)是过程Quick_Sort作用于规模为n的输入上的最坏情况的时间，则
T(n)=max(T(q)+T(n-q))+θ(n) ,其中1≤q≤n-1    (2)
我们假设对于任何k<n，总有T(k)≤ck2 ，其中c为常数；显然当k=1时是成立的。
将归纳假设代入(2)，得到：
T(n)≤max(cq2+c(n-q)2)+θ(n)=c*max(q2+(n-q)2)+θ(n)
因为在[1,n-1]上q2+(n-q)2关于q递减，所以当q=1时q2+(n-q)2有最大值n2-2(n-1)。于
是有：
T(n)≤cn2-2c(n-1)+θ(n)≤cn2
只要c足够大，上面的第二个小于等于号就可以成立。于是对于所有的n都有T(n)≤cn2 
。
这样，排序算法的最坏情况运行时间为θ(n2)，且最坏情况发生在每次划分过程产生的
两个区间分别包含n-1个元素和1个元素的时候。
最好情况
如果每次划分过程产生的区间大小都为n/2，则快速排序法运行就快得多了。这时有：
T(n)=2T(n/2)+θ(n), T(1)=θ(1)     (3)
解得： T(n)=θ(nlogn)
快速排序法最佳情况下执行过程的递归树如下图所示，图中lgn表示以2位底的对数，而
本文中用logn表示以2位底的对数.
图2  快速排序法最佳情况下执行过程的递归树
　
由于快速排序法也是基于比较的排序法，其运行时间为Ω(nlogn)，所以如果每次划分过
程产生的区间大小都为n/2，则运行时间θ(nlogn)就是最好情况运行时间。
但是，是否一定要每次平均划分才能达到最好情况呢？要理解这一点就必须理解对称性
是如何在描述运行时间的递归式中反映的。我们假设每次划分过程都产生9:1的划分，乍
一看该划分很不对称。我们可以得到递归式：
T(n)=T(n/10)+T(9n/10)+θ(n) , T(1)=θ(1)         (4)
这个递归式对应的递归树如下图所示：
图3  (4)式对应的递归树
　
请注意该树的每一层都有代价n，直到在深度log10n=θ(logn)处达到边界条件， 以后各
层代价至多为n。递归于深度log10/9n=θ(logn)处结束。这样，快速排序的总时间代价
为T(n)=θ(nlogn)，从渐进意义上看就和划分是在中间进行的一样。事实上，即使是99
:1的划分时间代价也为θ(nlogn)。其原因在于，任何一种按常数比例进行划分所产生的
递归树的深度都为θ(nlogn)，其中每一层的代价为O(n)，因而不管常数比例是什么，总
的运行时间都为θ(nlogn)，只不过其中隐含的常数因子有所不同。(关于算法复杂性的
渐进阶，请参阅算法的复杂性)
平均情况
我们首先对平均情况下的性能作直觉上的分析。
要想对快速排序的平均情况有个较为清楚的概念，我们就要对遇到的各种输入作个假设
。通常都假设输入数据的所有排列都是等可能的。后文中我们要讨论这个假设。
当我们对一个随机的输入数组应用快速排序时，要想在每一层上都有同样的划分是不太
可能的。我们所能期望的是某些划分较对称，另一些则很不对称。事实上，我们可以证
明，如果选择L[p..r]的第一个元素作为支点元素，Partition所产生的划分80%以上都比
9:1更对称，而另20%则比9:1差，这里证明从略。
平均情况下，Partition产生的划分中既有“好的”，又有“差的”。这时，与Partiti
on执行过程对应的递归树中，好、差划分是随机地分布在树的各层上的。为与我们的直
觉相一致，假设好、差划分交替出现在树的各层上，且好的划分是最佳情况划分，而差
的划分是最坏情况下的划分，图4(a)表示了递归树的连续两层上的划分情况。在根节点
处，划分的代价为n，划分出来的两个子表的大小为n-1和1，即最坏情况。在根的下一层
，大小为n-1的子表按最佳情况划分成大小各为(n-1)/2的两个子表。这儿我们假设含1个
元素的子表的边界条件代价为1。
(a)
(b)
图4 快速排序的递归树划分中的两种情况
在一个差的划分后接一个好的划分后，产生出三个子表，大小各为1，(n-1)/2和(n-1)/
2，代价共为2n-1=θ(n)。这与图4(b)中的情况差不多。该图中一层划分就产生出大小为
(n-1)/2+1和(n-1)/2的两个子表，代价为n=θ(n)。这种划分差不多是完全对称的，比9
:1的划分要好。从直觉上看，差的划分的代价θ(n)可被吸收到好的划分的代价θ(n)中
去，结果是一个好的划分。这样，当好、差划分交替分布划分都是好的一样：仍是θ(n
logn)，但θ记号中隐含的常数因子要略大一些。关于平均情况的严格分析将在后文给出
。
在前文从直觉上探讨快速排序的平均性态过程中，我们已假定输入数据的所有排列都是
等可能的。如果输入的分布满足这个假设时，快速排序是对足够大的输入的理想选择。
但在实际应用中，这个假设就不会总是成立。
解决的方法是，利用随机化策略，能够克服分布的等可能性假设所带来的问题。
一种随机化策略是：与对输入的分布作“假设”不同的是对输入的分布作“规定”。具
体地说，在排序输入的线性表前，对其元素加以随机排列，以强制的方法使每种排列满
足等可能性。事实上，我们可以找到一个能在O(n)时间内对含n个元素的数组加以随机排
列的算法。这种修改不改变算法的最坏情况运行时间，但它却使得运行时间能够独立于
输入数据已排序的情况。
另一种随机化策略是：利用前文介绍的选择支点元素pivot的第四种方法，即随机地在L
[p..r]中选择一个元素作为支点元素pivot。实际应用中通常采用这种方法。
快速排序的随机化版本有一个和其他随机化算法一样的有趣性质：没有一个特别的输入
会导致最坏情况性态。这种算法的最坏情况性态是由随机数产生器决定的。你即使有意
给出一个坏的输入也没用，因为随机化排列会使得输入数据的次序对算法不产生影响。
只有在随机数产生器给出了一个很不巧的排列时，随机化算法的最坏情况性态才会出现
。事实上可以证明几乎所有的排列都可使快速排序接近平均情况性态,只有非常少的几个
排列才会导致算法的近最坏情况性态。
一般来说，当一个算法可按多条路子做下去，但又很难决定哪一条保证是好的选择时，
随机化策略是很有用的。如果大部分选择都是好的，则随机地选一个就行了。通常，一
个算法在其执行过程中要做很多选择。如果一个好的选择的获益大于坏的选择的代价，
那么随机地做一个选择就能得到一个很有效的算法。我们在前文已经了解到，对快速排
序来说，一组好坏相杂的划分仍能产生很好的运行时间。因此我们可以认为该算法的随
机化版本也能具有较好的性态。
在前文我们从直觉上分析了快速排序在平均情况下的性能为θ(nlogn)，我们将在下面定
量地分析快速排序法在平均情况下的性能。为了满足输入的数据的所有排列都是等可能
的这个假设，我们采用上面提到的随机选择pivot的方法，并且在Select_pivot函数中将
选出的pivot与L[p]交换位置（这不是必需的，纯粹是为了下文分析的方便，这样L[p]就
是支点元素pivot）。那种基于对输入数据加以随机排列的随机化算法的平均性态也很好
，只是比这儿介绍的这个版本更难以分析。
我们先来看看Partition的执行过程。为简化分析，假设所有输入数据都是不同的。即使
这个假设不满足，快速排序的平均情况运行时间仍为θ(nlogn)，但这时的分析就要复杂
一些。
由Partition返回的值q仅依赖于pivot在L[p..r]中的秩(rank)，某个数在一个集合中的
秩是指该集合中小于或等于该数的元素的个数。如果设n为L[p..r]的元素个数，将L[p]
与L[p..r]中的一个随机元素pivot交换就得rank(pivot)=i(i=1,2,..,n)的概率为l/n。

下一步来计算划分过程不同结果的可能性。如果rank(pivot)=1，即pivot是L[p..r]中最
小的元素，则Partition的循环结束时指针i停在i=p处，指针j停在k=p处。当返回q时，
划分结果的"低区"中就含有唯一的元素L[p]=pivot。这个事件发生的概率为1/n，因为r
ank(pivot)=i的概率为1/n。
如果rank(pivot)≥2，则至少有一个元素小于L[p]，故在外循环while循环的第一次执行
中，指针i停于i=p处，指针j则在达到p之前就停住了。这时通过交换就可将L[p]置于划
分结果的高区中。当Partition结束时，低区的rank(pivot)-1个元素中的每一个都严格
小于pivot（因为假设输入的元素不重复）。这样，对每个i=1,2,..,n-1，当rank(pivo
t)≥2时，划分的低区中含i个元素的概率为 l/n。
把这两种情况综合起来，我们的结论为：划分的低区的大小为1的概率为2/n，低区大小
为i的概率为1/n，i=2,3,..n-1。
现在让我们来对Quick_Sort的期望运行时间建立一个递归式。设T(n)表示排序含n个元素
的表所需的平均时间，则：
   （5）
其中T(1)=θ(1)。
q的分布基本上是均匀的，但是q=1的可能性是其他值的两倍。根据前面作的最坏情况的
分析有：
T(1)=θ(1),T(n-1)=θ(n2)，所以
这可被(5)式中的θ(n)所吸收，所以(5)式可简化为：
           (6)
注意对k=1,2,..,n-1，和式中每一项T(k)为T(q)和T(n-q)的机会各有一次，把这两项迭
起来有：
                        (7)
　
我们用代入法来解上述递归方程。归纳假设T(n)≤a*nlogn+b，其中a>0,b>0为待定常数
。可以选择足够大的a,b使anlogn+b>T(1)，对于n>1有：
          （8）
下面我们来确定和式
                    （9）
的界。
因为和式中每一项至多是nlogn，则有界：
这是个比较紧的界，但是对于解递归式（8）来说还不够强。为解该递归式，我们希望有
界：
为了得到这个界，可以将和式(9)分解为两部分，这时有：
等号右边的第一个和式中的logk可由log(n/2)=logn-1从上方限界。第二个和式中的log
k可由logn从上方限界，这样，
对于n≥2成立。即:
     (10)
将(10)代入(8）式得：
      （11）
　
因为我们可以选择足够大的a使a*n/4能够决定θ(n)+b，所以快速排序的平均运行时间为
θ(nlogn)。


大整数乘法
问题描述
通常，在分析一个算法的计算复杂性时，都将加法和乘法运算当作是基本运算来处理，
即将执行一次加法或乘法运算所需的计算时间当作一个仅取决于计算机硬件处理速度的
常数。
   这个假定仅在计算机硬件能对参加运算的整数直接表示和处理时才是合理的。然而，
在某些情况下，我们要处理很大的整数，它无法在计算机硬件能直接表示的范围内进行
处理。若用浮点数来表示它，则只能近似地表示它的大小，计算结果中的有效数字也受
到限制。若要精确地表示大整数并在计算结果中要求精确地得到所有位数上的数字，就
必须用软件的方法来实现大整数的算术运算。
   请设计一个有效的算法，可以进行两个n位大整数的乘法运算。
参考解答

大整数的乘法
问题描述
参考解答
设X和Y都是n位的二进制整数，现在要计算它们的乘积XY。我们可以用小学所学的方法来
设计一个计算乘积XY的算法，但是这样做计算步骤太多，显得效率较低。如果将每2个1
位数的乘法或加法看作一步运算，那么这种方法要作O(n2)步运算才能求出乘积XY。下面
我们用分治法来设计一个更有效的大整数乘积算法。
　
图6-3 大整数X和Y的分段　
我们将n位的二进制整数X和Y各分为2段，每段的长为n/2位(为简单起见，假设n是2的幂
)，如图6-3所示。
由此，X=A2n/2+B ，Y=C2n/2+D。这样，X和Y的乘积为：
XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+CB)2n/2+BD             (1)
如果按式(1)计算XY，则我们必须进行4次n/2位整数的乘法(AC，AD，BC和BD)，
以及3次不超过n位的整数加法(分别对应于式(1)中的加号)，此外还要做2次移位(分别对
应于式(1)中乘2n和乘2n/2)。所有这些加法和移位共用O(n)步运算。设T(n)是2个n位整
数相乘所需的运算总数，则由式(1)，我们有:
                             (2)
由此可得T(n)=O(n2)。因此，用(1)式来计算X和Y的乘积并不比小学生的方法更有效。要
想改进算法的计算复杂性，必须减少乘法次数。为此我们把XY写成另一种形式:
XY=AC2n+[(A-B)(D-C)+AC+BD]2n/2+BD                     (3)
虽然，式(3)看起来比式(1)复杂些，但它仅需做3次n/2位整数的乘法(AC，BD和(A-B)(D
-C))，6次加、减法和2次移位。由此可得:
                                 (4)
用解递归方程的套用公式法马上可得其解为T(n)=O(nlog3)=O(n1.59)。利用式(3)，并考
虑到X和Y的符号对结果的影响，我们给出大整数相乘的完整算法MULT如下:
function MULT(X，Y，n); {X和Y为2个小于2n的整数，返回结果为X和Y的乘积XY}begin
  S:=SIGN(X)*SIGN(Y); {S为X和Y的符号乘积}  X:=ABS(X);  Y:=ABS(Y); {X和Y分别取
绝对值}  if n=1 then     if (X=1)and(Y=1) then return(S)                    
  else return(0)         else begin                A:=X的左边n/2位;         
       B:=X的右边n/2位;                C:=Y的左边n/2位;                D:=Y的
右边n/2位;                ml:=MULT(A,C,n/2);                m2:=MULT(A-B,D-C
,n/2);                m3:=MULT(B,D,n/2);                S:=S*(m1*2n+(m1+m2+m
3)*2n/2+m3);                return(S);              end;end;
上述二进制大整数乘法同样可应用于十进制大整数的乘法以提高乘法的效率减少乘法次
数。下面的例子演示了算法的计算过程。
设X=314l,Y=5327，用上述算法计算XY的计算过程可列表如下，其中带'号的数值是在计
算完成AC，BD，和(A-B)(D-C)之后才填入的。
----------------------------------------------------------------------------
----
X=3141        A=31       B=41        A-B=-10
Y=5327        C=53       D=27        D-C=-26
           AC=(1643)'
           BD=(1107)'
          (A-B)(D-C)=(260)'
XY=(1643)'104+[(1643)'+(260)'+(1107)']102+(1107)'
  =(16732107)'
----------------------------------------------------------------------------
----
A=31        A1=3       B1=1        A1-B1=2
C=53        C1=5       D1=3        D1-C1=-2
           A1C1=15     B1D1=3     (A1-B1)(D1-C1)=-4
AC=1500+(15+3-4)10+3=1643
----------------------------------------------------------------------------
----
B=41        A2=4       B2=1        A2-B2=3
D=27        C2=2       D2=7        D2-C2=5
           A2C2=8     B2D2=7     (A2-B2)(D2-C2)=15
BD=800+(8+7+15)10+7=1107
----------------------------------------------------------------------------
----
|A-B|=10        A3=1       B3=0        A3-B3=1
|D-C|=26        C3=2       D3=6        D3-C3=4
           A3C3=2     B3D3=0     (A3-B3)(D3-C3)=4
(A-B)(D-C)=200+(2+0+4)10+0=260
----------------------------------------------------------------------------
----
如果将一个大整数分成3段或4段做乘法，计算复杂性会发生会么变化呢?是否优于分成2
段做的乘法？这个问题请大家自己考虑。



Strassen矩阵乘法
矩阵乘法是线性代数中最常见的运算之一，它在数值计算中有广泛的应用。若A和B是2个
n×n的矩阵，则它们的乘积C=AB同样是一个n×n的矩阵。A和B的乘积矩阵C中的元素C[i
,j]定义为:　
若依此定义来计算A和B的乘积矩阵C，则每计算C的一个元素C[i,j]，需要做n个乘法和n
-1次加法。因此，求出矩阵C的n2个元素所需的计算时间为0(n3)。
60年代末，Strassen采用了类似于在大整数乘法中用过的分治技术，将计算2个n阶矩阵
乘积所需的计算时间改进到O(nlog7)=O(n2.18)。
首先，我们还是需要假设n是2的幂。将矩阵A，B和C中每一矩阵都分块成为4个大小相等
的子矩阵，每个子矩阵都是n/2×n/2的方阵。由此可将方程C=AB重写为:
　(1)
由此可得:　
C11=A11B11+A12B21                           (2)
C12=A11B12+A12B22                           (3)
C21=A21B11+A22B21                           (4)
C22=A21B12+A22B22                           (5)
如果n=2，则2个2阶方阵的乘积可以直接用(2)-(3)式计算出来，共需8次乘法和4次加法
。当子矩阵的阶大于2时，为求2个子矩阵的积，可以继续将子矩阵分块，直到子矩阵的
阶降为2。这样，就产生了一个分治降阶的递归算法。依此算法，计算2个n阶方阵的乘积
转化为计算8个n/2阶方阵的乘积和4个n/2阶方阵的加法。2个n/2×n/2矩阵的加法显然可
以在c*n2/4时间内完成，这里c是一个常数。因此，上述分治法的计算时间耗费T(n)应该
满足：
这个递归方程的解仍然是T(n)=O(n3)。因此，该方法并不比用原始定义直接计算更有效
。究其原因，乃是由于式(2)-(5)并没有减少矩阵的乘法次数。而矩阵乘法耗费的时间要
比矩阵加减法耗费的时间多得多。要想改进矩阵乘法的计算时间复杂性，必须减少子矩
阵乘法运算的次数。按照上述分治法的思想可以看出，要想减少乘法运算次数，关键在
于计算2个2阶方阵的乘积时，能否用少于8次的乘法运算。Strassen提出了一种新的算法
来计算2个2阶方阵的乘积。他的算法只用了7次乘法运算，但增加了加、减法的运算次数
。这7次乘法是:　
M1=A11(B12-B22)
M2=(A11+A12)B22
M3=(A21+A22)B11
M4=A22(B21-B11)
M5=(A11+A22)(B11+B22)
M6=(A12-A22)(B21+B22)
M7=(A11-A21)(B11+B12)
做了这7次乘法后，再做若干次加、减法就可以得到:　
C11=M5+M4-M2+M6
C12=M1+M2
C21=M3+M4
C22=M5+M1-M3-M7
以上计算的正确性很容易验证。例如:　
C22=M5+M1-M3-M7
   =(A11+A22)(B11+B22)+A11(B12-B22)-(A21+A22)B11-(A11-A21)(B11+B12)
   =A11B11+A11B22+A22B11+A22B22+A11B12
     -A11B22-A21B11-A22B11-A11B11-A11B12+A21B11+A21B12
   =A21B12+A22B22　
由(2)式便知其正确性。
至此，我们可以得到完整的Strassen算法如下：
procedure STRASSEN(n,A,B,C);begin  if n=2 then MATRIX-MULTIPLY(A，B，C)     
    else begin                将矩阵A和B依(1)式分块;                STRASSEN
(n/2,A11,B12-B22,M1);                STRASSEN(n/2,A11+A12,B22,M2);          
      STRASSEN(n/2,A21+A22,B11,M3);                STRASSEN(n/2,A22,B21-B11,
M4);                STRASSEN(n/2,A11+A22,B11+B22,M5);                STRASSE
N(n/2,A12-A22,B21+B22,M6);                STRASSEN(n/2,A11-A21,B11+B12,M7);
                    ;
               end;
end;
其中MATRIX-MULTIPLY(A，B，C)是按通常的矩阵乘法计算C=AB的子算法。
Strassen矩阵乘积分治算法中，用了7次对于n/2阶矩阵乘积的递归调用和18次n/2阶矩阵
的加减运算。由此可知，该算法的所需的计算时间T(n)满足如下的递归方程:
按照解递归方程的套用公式法，其解为T(n)=O(nlog7)≈O(n2.81)。由此可见，Strasse
n矩阵乘法的计算时间复杂性比普通矩阵乘法有阶的改进。
有人曾列举了计算2个2阶矩阵乘法的36种不同方法。但所有的方法都要做7次乘法。除非
能找到一种计算2阶方阵乘积的算法，使乘法的计算次数少于7次，按上述思路才有可能
进一步改进矩阵乘积的计算时间的上界。但是Hopcroft和Kerr(197l)已经证明，计算2个
2×2矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就
不能再寄希望于计算2×2矩阵的乘法次数的减少。或许应当研究3×3或5×5矩阵的更好
算法。在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计
算时间上界是O(n2.367)。而目前所知道的矩阵乘法的最好下界仍是它的平凡下界Ω(n2
)。因此到目前为止还无法确切知道矩阵乘法的时间复杂性。关于这一研究课题还有许多
工作可做。



最接近点对问题
问题描述
在应用中，常用诸如点、圆等简单的几何对象代表现实世界中的实体。在涉及这些几何
对象的问题中，常需要了解其邻域中其他几何对象的信息。例如，在空中交通控制问题
中，若将飞机作为空间中移动的一个点来看待，则具有最大碰撞危险的2架飞机，就是这
个空间中最接近的一对点。这类问题是计算几何学中研究的基本问题之一。下面我们着
重考虑平面上的最接近点对问题。
最接近点对问题的提法是:给定平面上n个点，找其中的一对点，使得在n个点的所有点对
中，该点对的距离最小。
严格地说，最接近点对可能多于1对。为了简单起见，这里只限于找其中的一对。
导线和开关
问题描述
如图1所示，具有3根导线的电缆把A区和B区连接起来。在A区3根导线标以1，2，3；在B
区导线1和3被连到开关3，导线2连到开关1。
图1 一个有3条导线和3个开关的实例
一般说来，电缆含m(1<=m<=90)根导线，在A区标以1,2,...,m。在B区有m个开关，标为1
,2,..,m。每一根导线都被严格地连到这些开关中的某一个上；每一个开关上可以连有0
根或多根导线。
你的程序应作某些测量来确定导线和开关怎样连。每个开关或处于接通或处于断开状态
，开关的初始状态为断开。我们可用一个探头P在A区进行测试：如果探头点到某根导线
上，当且仅当该导线连到处于接通状态的开关时，灯L才会点亮。
你的程序从标准输入读入一行以得到数字m；然后可以通过向标准输出写入一行以发出命
令(共3种命令)。每种命令的开头是一个大写字母:
测试导线命令T：T后面跟一个导线标号；
改变开关状态命令C：C后面跟一个开关标号；
完成命令D：D后面跟的是一个表列，该表列中的第i个元素代表与导线i相连的开关号。

在命令T和C之后，你的程序应从标准输入读入一行。若开关状态能使灯亮，则命令T的回
答应是Y；反之，回答应是N。命令C的作用是改变开关的状态(若原来是接通则变为断开
；若原来是断开则变为接通)。对C命令的回答是作为一种反馈信号。
你的程序可以给出一系列命令，将T命令与C命令以任意顺序混合使用。最后给出命令D，
并结束。你的程序给出的命令总数应不大于900。
举例：图2给出了一个实例，对应于图1，这是一个有8条命令的对话。
____________________________________
| Standard Output | Standard Input |
|_________________|________________|
__________________| 3              |
| C 3             | Y              |
| T 1             | Y              |
| T 2             | N              |
| T 3             | Y              |
| C 3             | N              |
| C 2             | Y              |
| T 2             | N              |
| D 3 1 3         |________________|
|_________________|
   图2  对应于图1的8条命令的实例
说明：本题为IOI'95 第二天的第三题。



--
　　不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]