本文通过讲解3个基本问题的应用，提供了分治算法设计范式的实践。第一个例子是对数组中的逆序对进行计数的算法（第3.2节）。这个问题与测量两个有序列表的相似性有关，适用于根据自己的知识向其他人按照他们的偏好提供优质的推荐（称为“协同筛选”）。第二个分治算法的例子是Strassen所发明的令人兴奋的矩阵相乘递归算法，它与迭代方法（第3.3节）相比，性能提升非常明显。第三个算法属于高级的选修知识，用于解决计算几何学的一个基本问题：计算平面上最近的点对（第3.4节）。

3.1　分治法规范

我们已经看过分治算法的一个经典例子：MergeSort（第1.4节）。概括地说，分治算法设计范式一般具有3个概念步骤。

分治范式

1．把输入划分为更小的子问题。

2．递归地治理子问题。

3．把子问题的解决方案组合在一起，形成原始问题的解决方案。

例如，在MergeSort中，“划分”步骤把输入数组分成左半部分和右半部分，“治理”步骤是由Merge子程序（第1.4.5节）所实现的。在MergeSort和许多其他算法中，需要用到巧妙思维的时机正是在这最后一步。也有些分治算法的巧妙之处出现在第一个步骤（参见第5章的QuickSort）或者出现在递归调用的规格说明中（参见第3.2节）。

3.2　以O(n log n)时间计数逆序对

3.2.1　问题

本节研究对一个数组中的逆序对计数的问题。所谓数组的逆序对，就是指一对元素“乱了序”，也就是出现在数组较前位置的元素比出现在较后位置的元素更大。

问题：对逆序对进行计数

输入：一个包含不同整数的数组A。

输出：A中的逆序对数量，即数组中符合i < j并且A[i] > A[j]的(i, j)对的数量。

例如，已经排序的数组A没有任何逆序对。反过来的说法也是对的，未排序的数组至少有1对逆序对。

3.2.2　一个例子

考虑下面这个长度为6的数组：

这个数组有几个逆序对呢？显而易见的一个例子就是5和2（分别对应于i=3和j=4）。这个数组还有另外2对逆序对：3和2以及5和4。

小测验3.1

包含6个元素的数组最多可能出现几对逆序对？

（a）15

（b）21

（c）36

（d）64

（关于正确答案和详细解释，参见第3.2.13节）

3.2.3　协同筛选

为什么需要对数组中的逆序对进行计数呢？一个原因是想要计算一种数值相似度，该数值相似度用于对两个已排序列表之间的相似程度进行量化。例如，读者邀请一位朋友一起对两人都看过的10部电影按照从最喜欢到最不喜欢的顺序进行排列。怎么衡量两人的选择是“相似”或“不同”呢？解决这个问题的一种量化方法是通过一个包含10个元素的数组A：A[1]表示读者的朋友从电影列表中所选择的最喜欢的电影，A[2]表示他其次喜欢的电影，以此类推，A[10]表示他最不喜欢的电影。这样，如果读者最喜欢的电影是《星球大战》，而这部电影在读者朋友的列表中只是出现在第5位，那么A[1] = 5。如果两人的排序是相同的，这个数组就是已经排序的，不存在逆序对。这个数组包含的逆序对越多，读者和朋友之间对电影评价的分歧就越多，对电影的偏好也更加不同。

对已排序列表进行相似性测量的一个原因是进行协同筛选，这是一种用于生成推荐方案的方法。网站怎么推出关于产品、电影、歌曲、新闻故事等内容的建议呢？在协同筛选中，其思路是寻找其他具有相似偏好的用户，然后推荐他们所喜欢的内容。因此协同筛选需要用户之间“相似性”的形式定义，而计算逆序对能够捕捉到这个问题的一些本质。

3.2.4　穷举搜索法

计算数组的逆序对数量的速度有多快？如果对此缺乏概念，那可以尝试使用穷举搜索法。

用穷举搜索法对逆序对进行计数

输入：包含n个不同整数的数组A。

输出：A中逆序对的数量。

numInv := 0for i := 1 to n − 1 do　　for j := i + 1 to n do　　　　if A[i] > A[j] then　　　　　　numInv := numInv + 1return numInv

显然，这是一种正确的算法。它的运行时间是什么？根据小测验3.1的答案，我们知道循环的迭代次数与输入数组的长度n的平方成正比。由于这种算法每次迭代时执行的操作数量是常数级的，因此它的渐进性运行时间是Θ(n2)。记住，经验丰富的算法设计师的座右铭是：“还能做得更好吗？”

3.2.5　分治法

答案是肯定的，解决方案是运行时间为O(n log n)的分治算法，它的性能较之穷举搜索法有了很大的提高。它的“划分”步骤和MergeSort算法的完全一样，一个递归调用作用于数组的左半边，另一个递归调用作用于数组的右半边。为了理解这两个递归调用之外所需要完成的剩余工作，我们把一个长度为n的数组A中的逆序对(i, j)分为3类。

（1）左逆序对：逆序对的i和j都位于数组的左半部分（即

）。

（2）右逆序对：逆序对的i和j都位于数组的右半部分（即

）。

（3）分离逆序列：逆序对的i位于数组的左半部分，j位于数组的右半部分（即

）。

例如，在第3.2.2节的那个6元素数组例子中，3个逆序对都是分离逆序对。

第1个递归调用作用于输入数组的左半部分，它采用递归的方式对左逆序对进行计数（没有其他任何操作）。类似，第2个递归调用对所有的右逆序对进行计数。剩余的任务是对那些并没有被这两个递归调用所计数的逆序对（即分离逆序对）进行计数。这是这个算法的“组合”步骤，我们需要为它实现一种特殊的线性时间的子程序，类似于MergeSort算法中的Merge子程序。

3.2.6　高级算法

我们的分治算法可以翻译为下面的伪码，用于计数分离逆序对的CountSplitInv子程序目前还没有实现。

CountInv

输入：包含n个不同整数的数组A。

输出：A中逆序对的数量。

if n = 0 or n = 1 then // 基本条件　　return 0else　　leftInv := CountInv(first half of A)　　rightInv := CountInv(second half of A)　　splitInv := CountSplitInv(A)　　return leftInv + rightInv + splitInv

第一个和第二个递归调用分别对左逆序对和右逆序对进行计数。假如CountSplitInv子程序可以正确地对分离逆序对进行计数，CountInv就可以正确地计算逆序对的总数。

3.2.7　关键思路：站在MergeSort的肩膀上

要想使对数组的分离逆序对进行计数的算法具有线性运行时间是个很有雄心的目标。分离逆序对的数量可能很多：如果A按顺序包含了

，然后按顺序又包含了

，那么一共就有

个分离逆序对。我们怎么才能在线性工作时间内完成平方级数量的工作呢？

思路就是在设计递归式计数逆序对的算法时站在MergeSort算法的肩膀之上。它除了递归调用之外还需要完成一些任务，才能更方便地计数分离逆序对的数量[2]。每个递归调用不仅负责对指定部分的数组中的逆序对进行计数，而且要返回该数组的排序版本。我们已经知道（通过定理1.2）排序是一种可以尽情使用的基本操作，其运行时间为O(n log n)。因此，如果我们所争取的运行时间上限为O(n log n)，那么有什么理由不进行排序呢？我们很快就会看到，对两个已经排序的子数组进行归并这个任务简直就是为对数组中的分离逆序对进行计数这个任务量身定做的。

下面是第3.2.6节的伪码经过修订的版本，它在计数的同时还对数组进行排序。

Sort-and-CountInv

输入：包含n个不同整数的数组A。

输出：包含与A中相同整数的、已经排序的数组B，以及数组A中的逆序对的数量。

if n = 0 or n = 1 then // 基本条件　　return (A; 0)else　　(C; leftInv) := Sort-and-CountInv(first half of A)　　(D; rightInv) := Sort-and-CountInv(second half of A)　　(B; splitInv) := Merge-and-CountSplitInv(C;D)　　return (B; leftInv + rightInv + splitInv) 

我们仍然需要实现Merge-and-CountSplitInv子程序。我们知道如何用线性时间对两个已经排序的列表进行归并，但是怎么才能利用这个成果对分离逆序对进行计数呢？

3.2.8　重温Merge

为了观察为什么合并已经排序的数组可以自然地发现分离逆序对，我们重新回顾一下Merge子程序的伪码。

Merge

输入：已经排序的数组C和D（长度分别为n/2）。

输出：已经排序的数组B（长度为n）。

用于简化问题的先决条件：n是偶数。

i := 1, j := 1for k := 1 to n do　　if C[i] < D[j] then　　　　B[k] := C[i], i := i + 1　　else　　　　　　　　　　　　　// D[j] < C[i]　　　　B[k] := D[j], j := j + 1

重温一下，Merge子程序根据索引平行地（用i访问C，用j访问D）访问每个已经排序的子数组，并按从左向右的排序顺序生成输出数组B（使用索引k）。

在循环的每次迭代中，这个子程序寻找目前为止尚未被复制到B中的最小元素。由于C和D都已经排序，所以C[i]和D[j]之前的所有元素都已经被复制到B中，仅有的两个候选元素就是C[i]和D[j]。Merge子程序判断这两个元素哪个更小，并把它复制到输出数组的下一个位置。

如果需要计算分离逆序对的数量，Merge子程序需要做些什么呢？我们首先讨论一种特殊的情况，就是数组A中不包含任何分离逆序对，A中的每个逆序对要么是左逆序对，要么是右逆序对。

小测验3.2

假设输入数组A不存在分离逆序对，那么已经排序的子数组C和D之间存在什么关系？

（a）C包含A中最小的元素，D包含第二小的，C包含第三小的，依次类推。

（b）C的所有元素都小于D的任何元素。

（c）C的所有元素都大于D的任何元素。

（d）没有足够的信息可以回答这个问题。

（关于正确答案和详细解释，参见第3.2.13节）

在解决了小测验3.2之后，我们可以看到Merge在数组不存在分离逆序对时会执行一些特别无聊的操作。由于C的每个元素都小于D的每个元素，所以最小的元素总是出现在C中（除非C中不再剩下任何元素）。因此Merge子程序只是把C和D连接在一起，它首先复制C的所有元素，然后复制D的所有元素。这是不是意味着当D的一个元素被复制到输出数组时，分离逆序对与C中剩余元素的数量有关呢？

3.2.9　Merge和分离逆序对

为了进一步证明自己的直觉，我们考虑对一个包含6个元素的数组A={1, 3, 5, 2, 4, 6}（来自第3.2.2节）运行MergeSort算法，参见图3.1。这个数组的左半部分和右半部分都已经排序，因此不存在左逆序对和右逆序对，两个递归调用都返回0。在Merge子程序的第1次迭代时，C的第1个元素（1）被复制到B。此时没有任何与分离逆序对有关的信息，事实上这个元素也与分离逆序对没有任何关系。但是，在第2次迭代时，“2”被复制到输出数组中，但此时C中仍然剩下元素3和5。这就说明了A中有2个分离逆序对，也就是与2相关联的两个逆序对。在第3次迭代时，3从C被复制到B，此时没有其他分离逆序对与这个元素有关。当4从D被复制到B时，数组C中仍然还有一个元素5，提示A中还有第3个也就是最后一个分离逆序对（元素5和元素2）。

图3.1　Merge子程序的第4次迭代面对的是已经排序的子数组{1, 3, 5}和{2, 4, 6}。从D复制元素“4”，此时“5”仍然留在C中，显示了与这两个元素相关的分离逆序对

下面这个辅助结论表示上面这个例子的模式可以推及到一般情况：在Merge子程序把第2个子数组D中的元素y复制到输出数组的当次迭代时，与y有关的分离逆序对的数量就是此时C中仍然剩余的元素的数量。

辅助结论3.1　 假设A是个数组，C和D分别是该数组左半部分和右半部分已经排序的子数组。A中左半部分的元素x和A中右半部分的元素y当且仅当下面这种情况成立时才能构成一对逆序对：在Merge子程序中输入C和D，y在x之前被复制到输出数组。

证明：由于输出数组是按从左向右的顺序生成的，因此x或y中较小的那个先被复制。由于x位于A的左半部分，y位于右半部分，因此当且仅当x > y时x和y才会构成一对逆序对，也就是当且仅当y在x之前被复制到输出数组中时x和y才会构成一对逆序对。Q.e.d.

3.2.10　Merge_and_CountSplitInv

根据辅助结论3.1所提供的结论，我们可以对Merge的实现进行扩展，实现Merge-and-CountSplitInv。

我们用一个变量记录分离逆序对的当前计数，每次当一个元素从右半部分的子数组D复制到输出数组B时，就把当前计数加上左半部分的子数组C中仍然剩余的元素数量。

Merge-and-CountSplitInv

输入：已经排序的数组C和D（长度均为n/2）。

输出：已经排序的数组B（长度为n）以及分离逆序对的数量。

用于简化问题的先决条件：n是偶数。

i := 1, j := 1, splitInv := 0for k := 1 to n do　　if C[i] < D[j] then　　　　B[k] := C[i], i := i + 1　　else　　　　　　　　　　　　　 // D[j] < C[i]　　　　B[k] := D[j], j := j + 1　　　　splitInv := splitInv + 

　　　　　　　　　　　　　　 #C中剩余元素的数量return (B; splitInv)

3.2.11　正确性

Merge-and-CountSplitInv的正确性是由辅助结论3.1所保证的。每个分离逆序对只涉及第2个子数组中的1个元素，并且当y被复制到输出数组时，这个逆序对正好被计数1次。整个Sort-and-CountInv算法（第3.2.7节）的正确性取决于下面的条件是否都得到满足：第1个递归调用正确地计算左逆序对的数量，第2个递归调用正确地计算右逆序对的数量，Merge-and- CountSplitInv返回剩余逆序对（分离逆序对）的正确数量。

3.2.12　运行时间

我们还可以借助前面已经完成的MergeSort算法运行时间的分析，对Sort-and- CountInv算法的运行时间进行分析。首先考虑单次调用Merge-and-CountSplitInv的运行时间，提供给它的是2个长度为

的子数组。和Merge子程序一样，它在循环的每次迭代时执行常数级的操作，另外还有一些常数级的其他操作，运行时间为O(

)。

回顾第1.5节对MergeSort算法运行时间的分析，我们可以看到这个算法具有3个重要的属性，导致它的运行时间上界是O(n log n)。首先，这个算法的每次调用都产生两个递归调用。其次，每一层递归调用的输入长度只有上一层的一半。最后，每个递归调用所完成的工作与输入长度呈正比（不包括下层递归调用所完成的工作）。

由于Sort-and-CountInv算法具有这些属性，所以第1.5节的分析对它也是适用的，因此它的运行时间上界是O(n log n)。

定理3.2（计数逆序对）对于长度大于等于1的数组A，Sort-and-CountInv算法计算A中逆序对的数量运行时间是O(n log n)。

3.2.13　小测验3.1～3.2的答案

小测验3.1的答案

正确答案（a）。这个问题的正确答案是15。逆序对的最大可能数量就是

中满足i<j的( i、j ) 对的数量。这个数量用

表示，意思是“6中选2”。一般而言

，因此

=15[3]。在一个反序排列的6元素数组（6, 5, 4, 3, 2, 1）中，每一对元素都是逆序的，因此这个数组一共有15个逆序对。

小测验3.2的答案

正确答案（b）。在不包含分离逆序对的数组中，左半部分数组中的所有元素都小于右半部分数组中的所有元素。如果左半部分数组中的某个元素A[i]（

）大于右半部分数组中的某个元素A[j]（

），则(i, j)就构成分离逆序对。

3.3　Strassen的矩阵相乘算法

本节把分治算法设计范式应用于矩阵相乘这个问题，这类算法的巅峰无疑是Strassen的矩阵相乘算法，它的运行时间令人吃惊，竟然低于立方级。这个算法是精巧的算法设计发挥神奇威力的一个典型例子。它可以让我们看到精妙的算法是怎样把简单解决方案远远抛在身后的，即使是对于极端基本的问题。

3.3.1　矩阵相乘

假设X和Y是

的整数矩阵，每个矩阵包含

个元素。在矩阵的乘积Ｚ＝Ｘ ·Ｙ中，Z中第i行第j列的元素Zij被定义为X的第i行和Y的第j列的数量积[4] （见图3.2）。即

（3.1）

图3.2　矩阵乘积X · Y的(i, j)项是X的第i行和Y的第j列的数量积

3.3.2　例子（n = 2）

现在我们来深入探讨n = 2这种情况。我们可以用8个参数来描述两个2×2的矩阵：

在矩阵的乘积X · Y中，左上角的元素是X的第1行和Y的第1列的数量积，即

。一般而言，对于像上面这样的矩阵X和Y，

（3.2）

《算法详解（卷1）——算法基础》

作者：[美] 科里•奥尔索夫（Cory Althoff）

这本书在美亚评分4.7，在作者的在线算法课程的基础之上编写的，是四卷本系列的第1卷。这个在线课程2012年起就定期更新，它建立在作者在斯坦福大学教授多年的本科课程的基础之上。也许你有所耳闻，这本书就是《算法详解（卷1）——算法基础》。如果你更喜欢听和看，可以在YouTobe上搜索这本书的主题课程，免费观看。

《算法详解（卷1）——算法基础》作者蒂姆·拉夫加登（Tim Roughgarden）是斯坦福大学计算机科学系的教授,也是该校管理科学和工程系的客座教授，他从2004年开始教授和研究算法。本书是他的《算法详解》四部曲的第一卷。

这本书详细讲解算法基础，展现算法本质 ,是一本囊括基本算法知识的详解指南。集斯坦福大学教授多年教学经验，深入浅出，通俗易懂。