29 分治算法

宋涛收录于 Python

2018-11-05 约 1295 字预计阅读 3 分钟

编程思想之分治算法

1. 分治算法

分治算法（divide and conquer）的核心思想其实就是四个字，分而治之，也就是将原问题划分成 n 个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。

这个定义看起来有点类似递归的定义。关于分治和递归的区别，我们在排序（下）的时候讲过，分治算法是一种处理问题的思想，递归是一种编程技巧。实际上，分治算法一般都比较适合用递归来实现。分治算法的递归实现中，每一层递归都会涉及这样三个操作：

分解：将原问题分解成一系列子问题；
解决：递归地求解各个子问题，若子问题足够小，则直接求解；
合并：将子问题的结果合并成原问题。

1.1 适用情景

分治算法能解决的问题，一般需要满足下面这几个条件：

原问题与分解成的小问题具有相同的模式；
原问题分解成的子问题可以独立求解，子问题之间没有相关性，这一点是分治算法跟动态规划的明显区别，等我们讲到动态规划的时候，会详细对比这两种算法；
具有分解终止条件，也就是说，当问题足够小时，可以直接求解；
可以将子问题合并成原问题，而这个合并操作的复杂度不能太高，否则就起不到减小算法总体复杂度的效果了。

1.2 分治在大数据中的应用

我们前面讲的数据结构和算法，大部分都是基于内存存储和单机处理。但是，如果要处理的数据量非常大，没法一次性放到内存中，这个时候，这些数据结构和算法就无法工作了。

要解决这种数据量大到内存装不下的问题，我们就可以利用分治的思想。将海量的数据集合根据某种方法，划分为几个小的数据集合，每个小的数据集合单独加载到内存来解决，然后再将小数据集合合并成大数据集合。实际上，利用这种分治的处理思路，不仅仅能克服内存的限制，还能利用多线程或者多机处理，加快处理的速度。

2.应用

归并排序和快速排序是分治算法的典型应用，这两个算法我们在之前的排序章节已经讲过了。所以我们以另一个例子: 如何编程求出一组数据的有序对个数或者逆序对个数，来讲解如何应用分治算法。

2.1 计算数据有序度

我们套用分治的思想来求数组 A 的逆序对个数。我们可以将数组分成前后两半 A1 和 A2，分别计算 A1 和 A2 的逆序对个数 K1 和 K2，然后再计算 A1 与 A2 之间的逆序对个数 K3。那数组 A 的逆序对个数就等于 K1+K2+K3。

使用分治算法其中一个要求是，子问题合并的代价不能太大，否则就起不了降低时间复杂度的效果了。那如何快速计算出两个子问题 A1 与 A2 之间的逆序对个数呢？这里就要借助归并排序算法了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


def reverse_count(A):
    """
    :param A:
    :return: 计算数组 A 的逆序度
    """
    if len(A) <= 1:
        return 0
    mid = len(A) // 2
    S1 = A[:mid]
    c1 = reverse_count(S1)
    S2 = A[mid:]
    c2 = reverse_count(S2)
    c3 = merge(S1, S2, A)
    return c1 + c2 + c3


def merge(S1, S2, S):
    """
    :param S1:
    :param S2:
    :param S:
    :return: 归并排序，并计算两个数组的逆序度
    """
    c = i = j = 0
    while i + j < len(S):
        if i == len(S1) or (j < len(S2) and S1[i] > S2[j]):
            S[i + j] = S2[j]
            j += 1
            c += (len(S1) - i)
        else:
            S[i + j] = S1[i]
            i += 1
    return c


s = [1, 5, 6, 7] + [2, 3, 4]
print reverse_count(s)
print s

3.练习

下面是分治算法的一些典型练习题

3.1 练习一

二维平面上有 n 个点，如何快速计算出两个距离最近的点对？

1

pass

3.2 练习二

有两个 n*n 的矩阵 A，B，如何快速求解两个矩阵的乘积 C=A*B？

1

pass

参考:

王争老师专栏-数据结构与算法之美

目录