算法学习笔记：分治法

2014-06-25

算法分治法

1. 分治法思想
2. 归并排序
1. 2.1 算法描述
2. 2.2 算法分析
3. 分治法案例

在计算机科学中，分治法是一种很重要的算法。分治法字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单地直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如归并排序、快速傅立叶变换等。

本文将简要介绍分治法的基本步骤，再以归并排序为例，介绍分治法的具体应用以及如何分析其时间复杂度。最后再介绍几个用分治法解决的算法案例。

1. 分治法思想

分治法所能解决的问题一般具有以下几个特征：

问题的规模缩小到一定的程度就可以容易地解决
问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质
利用该问题分解出的子问题的解可以合并为该问题的解
该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题

分治法的三个步骤是：

分解（Divide）：将原问题分解为若干子问题，这些子问题都是原问题规模较小的实例。
解决（Conquer）：递归地求解各子问题。如果子问题规模足够小，则直接求解。
合并（Combine）：将所有子问题的解合并为原问题的解

2. 归并排序

2.1 算法描述

归并排序（Merge Sort）完全遵循上述分治法三个步骤：

分解：将要排序的n个元素的序列分解成两个具有n/2个元素的子序列
解决：使用归并排序分别递归地排序两个子序列
合并：合并两个已排序的子序列，产生原问题的解

归并排序的算法思想，看看下面的图解示例就明白了。

归并排序图解

算法的主要过程代码如下所示：

def mergeSort(data):
# 分别归并排序左半部分和右半部分，再合并
if len(data) > 1:
    leftList = mergeSort(data[:len(data) / 2])
    rightList = mergeSort(data[len(data) / 2:])
    return merge(leftList, rightList)
# 递归中止条件：数组只有1个元素
else:
    return data

# 使用方法
result = mergeSort([2, 4, 7, 5, 8, 1, 3, 6])

注意上述代码只是归并排序的主要过程，其中最核心的是merge函数，它把两个已经有序的数组合并成一个有序数组。例如print merge([1, 3, 5], [2, 4, 6])将输出[1, 2, 3, 4, 5, 6]。合并过程非常简单，就是用两个指针分别指向两个子数组第一个元素，然后总是把小的数字填入结果中并将对应指针往右移一位；如果其中一个指针到头了，则直接把另外一个指针没到头的数组的剩余元素填入结果。

def merge(leftList, rightList):
result, i, j = [], 0, 0
# 合并完的数组的长度肯定是两个子数组的长度之和
for k in range(len(leftList) + len(rightList)):
    # 两个下标均在两个数组范围之内，则取小的填入结果数组
    if i < len(leftList) and j < len(rightList):
        if leftList[i] <= rightList[j]:
            result.append(leftList[i])
            i += 1
        else:
            result.append(rightList[j])
            j += 1
    # 最后可能其中一个数组还有剩余的部分，将其剩余部分依次填入结果数组
    else:
        result.append(leftList[i] if i < len(leftList) else rightList[j])
        i += 1
        j += 1
return result

2.2 算法分析

归并排序在元素的数量不是偶数的情况下也能正常工作，不过为了分析方便，我们假定原问题规模n是2的幂。下面我们分析归并排序n个数在最坏情况下的运行时间$T(n)$。按照分治法三部曲：分解仅计算子数组的中间位置，花费常量时间$\Theta (1)$；递归解决两个规模为n/2的子问题，总共花费$2T(n/2)$；合并两个长度为n/2的数组过程，注意到如果采用上述双指针的方法，每个元素最多只要访问一次就能合并完，因此花费$\Theta (n)$。另外，如果n=1时直接返回，花费常量时间$\Theta (1)$。所以归并排序最坏情况运行时间的递归式为：

$$T(n) = \cases{ {\Theta (1)} & n=1 \cr {2T(n/2) + \Theta (n)} & n>1 }$$

由上述归并排序图解可见，分解问题的过程实际上形成了一棵递归树。对于归并排序算法的递归树，假设树根（原问题）的规模为n（Level 0），则下一层有2个规模为n/2的子问题，再下一层有4个规模为n/4的子问题……

递归树一共有$\log n + 1$层，递归树的第$j$层（$j = 0,1, \cdots ,\log n$），一共有$2^j$个子问题，每个子问题的规模是$n/2^j$，解决该子问题所花费的时间为$\Theta (n/2^j)$。所以每一层所花时间为$2^j * \Theta (n/2^j) = \Theta (n)$，一共有$\log n$层，所以总的时间复杂度是$\Theta (nlogn)$。

当然，对于上面这种递归式，可以用一种通用的方法主方法（Master Method）来求解。关于主方法的说明会另外开一篇博文介绍。

3. 分治法案例

3.1 最大子数组问题

问题：一个包含n个整数（有正有负）的数组A，找出和最大的非空连续子数组。（例如：[0, -2, 3, 5, -1, 2]应返回9，[-9, -2, -3, -5, -3]应返回-2。）

基本解法：暴力求解找出所有子数组（$\Theta (n^2)$），对每个子数组求和（$\Theta (n)$），总复杂度是$\Theta (n^3)$。在遍历过程中，这些子数组的和是有重复计算的。下标i与j的区间和sum[i][j] = sum[i][j - 1] + A[j]，所以子数组求和变为$\Theta (1)$，时间复杂度降为$\Theta (n^2)$。

分治解法：要寻找A[left…right]的最大子数组，可以在中点mid处将A一分为二成A[left…mid]和A[mid+1…right]。A[left…right]的最大子数组必定是以下三者之一：

完全位于A[left…mid]
完全位于A[mid+1…right]
跨越了中点，即最大子数组的左边界落在left和mid之间，右边界落在mid和right之间

1和2两种情况可以通过递归调用来查找最大子数组，所以关键是3这个“合并”的步骤。因为跨越中点的子数组都由两个子数组A[i…mid]和A[mid…j]组成，所以我们可以从mid这个位置开始，分别向前和向后查找两个以mid为界的最大子数组，最后把这两个子数组合并成A[i…j]这个跨越中点的最大子数组即可。最后，问题的解就是上述三种情况里面和最大的那个子数组，总的时间复杂度是$\Theta (nlogn)$。

其实最大子数组问题还有DP解法和$\Theta (n)$的解法，详见这篇博文

$T(n) = O(f(n))$

3.2 逆序对问题

问题：给定一个长度为n的整数数组A，找出“逆序对”的个数。对下标i,j，当i<j时A[i]>A[j]，则(A[i], A[j])称为“逆序对”。（例如：[1, 3, 5, 2, 4, 6]的逆序对为(3,2), (5,2), (5,4)一共3个）

使用分治法找逆序对个数的思想其实和最大子数组问题几乎一样：把数组对半切分，递归统计左半部分的个数，右半部分的个数，以及跨越中点的个数（即i<mid<j），所以关键点还是在于如何实现子问题的合并。合并的时候像归并排序一样排序，例如在上例中，将[1,3,5]和[2,4,6]合并的同时，当j指向2时，i已指向3，此时剩余的3和5都可以组成反转数对；当j指向4时，i已指向5，此时5可以组成反转数对。依次类推，在合并过程中不断统计i及其右边剩余的个数。

3.3 Strassen矩阵乘法

问题：两个n*n的矩阵A和B相乘。

矩阵乘法公式：${z_{ij}} = \sum_{k=1}^n { {x_{ik} }{ y_{kj} } } $，时间复杂度为$\Theta (n^3)$。一种分治法将矩阵分成四块，如下所示：

$$X = \left[ {\matrix{
A & B \cr
C & D \cr
} } \right],Y = \left[ {\matrix{
E & F \cr
G & H \cr
} } \right],XY = \left[ {\matrix{
{AE + BG} & {AF + BH} \cr
{CE + DG} & {CF + DH} \cr
} } \right]$$

采用上述分块矩阵的做法，要递归调用8次，时间复杂度仍然为$\Theta (n^3)$。Strassen矩阵乘法是利用下述公式计算矩阵相乘：

$$ {P_1} = A(F - H),{P_2} = (A + B)H,{P_3} = (C + D)E,{P_4} = D(G - E) $$

$$ {P_5} = (A + D)(E + H),{P_6} = (B - D)(G + H),{P_7} = (A - C)(E + F) $$

$$XY = \left[ {\matrix{
{AE + BG} & {AF + BH} \cr
{CE + DG} & {CF + DH} \cr
} } \right] = \left[ { \matrix{
{ {P_5} + {P_4} - {P_2} + {P_7} } & { {P_1} + {P_2} } \cr
{ {P_3} + {P_4} } & { {P_1} + {P_5} - {P_3} - {P_7} } \cr
} } \right]$$

只需要递归调用7次即可。该算法时间复杂度约为$\Theta (n^{2.81})$，比$\Theta (n^3)$要更加理想。

参考文献：机械工业出版社《算法导论（第3版）》2.3节，第4章

上一篇：算法学习笔记：主方法

下一篇：算法学习笔记：渐进分析