算法学习笔记:分治法

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

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

1. 分治法思想

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

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

分治法的三个步骤是:

  1. 分解(Divide):将原问题分解为若干子问题,这些子问题都是原问题规模较小的实例。
  2. 解决(Conquer):递归地求解各子问题。如果子问题规模足够小,则直接求解。
  3. 合并(Combine):将所有子问题的解合并为原问题的解

2. 归并排序

2.1 算法描述

归并排序(Merge Sort)完全遵循上述分治法三个步骤:

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

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

归并排序图解

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

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]的最大子数组必定是以下三者之一:

  1. 完全位于A[left…mid]
  2. 完全位于A[mid+1…right]
  3. 跨越了中点,即最大子数组的左边界落在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章