分治算法（Divide ans conquer ,D&C）

前言

我之前看算法图解这本书，看他讲分治算法有一个很好的例子，我觉得这个例子让我理解分治的思想。

有一个农场主，想把一块长为168m，宽为64m的土地均匀的分成方块，要求分出的方块尽可能的最大。

1.首先的想法就是想划分一个最大的方块看行不行，以宽64m为边长，肯定是最大的方块。但是这样会剩下

40m的土地无法分割，于是转换思路。

2.把剩下的土地（40*64），在细分，适用于这小块的地方的最大的块也是适用于整块土地。后面这句话不好理解，于是我去查阅了欧几里得算法。

欧几里德算法（Euclidean algorithm），是求最大公约数的一种方法。它的具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。直接看下面的例子就懂了:

先看几个概念：

公约数，亦称“公因数”。它是指能同时整除几个整数的数。

公约数中最大的称为最大公约数

求104和40的最大公约数

1
2
3
4
5
104 % 40 = 24
40 % 24 = 16
24 % 16 = 8
16 % 8 = 0
结论：8就是104和40的最大公约数

回到划分土地，就转换成了，168和64的最大公约数，如下：

1
2
3
4
5
6
168 % 64 = 40
64 % 40 = 24
40 % 24 = 16
24 % 16 = 8
16 % 8 = 0
结论：8x8是划分的最大的

分治算法的意义

把一个较大的问题分解成几个较小的子问题，然后找到子问题的解决方法之后，再找到合适的方法，把他们组合起来最整个问题的解。

分治法适用的情况

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

  1. 该问题的规模缩小到一定的程度就可以容易地解决

  2. 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

  3. 利用该问题分解出的子问题的解可以合并为该问题的解；

  4. 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；

第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；、

第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。

第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

分治法的基本步骤

分治法在每一层递归上都有三个步骤：

1.分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

2.解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题

3.合并：将各个子问题的解合并为原问题的解。

实例

求最大数

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
# 基本子算法（子问题规模小于等于 2 时）
def get_max(max_list):
    # print(max_list)
    # return max(max_list)  # 这里偷个懒！
    return max_list[0] if max_list[0] > max_list[1] else max_list[1]


# 分治法
def solve2(init_list):
    n = len(init_list)
    if n <= 1:
        return init_list[0]
    if n < 2:  # 若问题规模小于等于 2，解决
        return get_max(init_list)

    # 分解（子问题规模为 n/2）
    left_list, right_list = init_list[:n // 2], init_list[n // 2:]

    # 递归（树），分治
    left_max, right_max = solve2(left_list), solve2(right_list)

    # 合并
    return get_max([left_max, right_max])


if __name__ == "__main__":
    # 测试数据
    test_list = [12, 2, 23, 45, 67, 3, 2, 4, 45, 63, 24, 23]
    # 求最大值
    print(solve2(test_list))  # 67

查找

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
# 子问题算法（子问题规模为 1）
def is_in_list(init_list, el):
     return [False, True][init_list[0] == el]

# 分治法
def solve(init_list, el):
     n = len(init_list)
     if n == 1:  # 若问题规模等于 1，直接解决
          return is_in_list(init_list, el)

     # 分解（子问题规模为 n/2）
     left_list, right_list = init_list[:n // 2], init_list[n // 2:]

     # 递归（树），分治，合并
     res = solve(left_list, el) or solve(right_list, el)

     return res


if __name__ == "__main__":
     # # 测试数据
     # test_list = [12, 2, 23, 45, 67, 3, 2, 4, 45, 63, 24, 23]
     # # 查找
     # print(solve(test_list, 45))  # True
     # print(solve(test_list, 5))  # F
     print(is_in_list([1,2,3], 1))

找到第n小的数

假定经过一趟分划后，长度为n的原表被分成两个左右两个子表，其中，长度为p的左子表包括主元及其左边的元素，右子表包括主元右边的元素。那么：

  • 若k=p，则主元即为第k小元素；
  • 若k<p ，第k小元素必定在左子表中，需求解的子问题成为在左子表中求第k小元素；
  • 若k>p，则第k小元素必定在右子表中，需求解的子问题成为在右子表中求第k-p小元素。
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
# 划分（基于主元 pivot），注意：非就地划分
def partition(seq):
    pi = seq[0]  # 挑选主元
    lo = [x for x in seq[1:] if x <= pi]  # 所有小的元素
    hi = [x for x in seq[1:] if x > pi]  # 所有大的元素
    return lo, pi, hi

# 查找第 k 小的元素
def select(seq, k):
    # 分解
    lo, pi, hi = partition(seq)
    print(lo, pi, hi)
    m = len(lo)
    if m == k- 1:
        return pi  # 解决！
    elif m < k:
        return select(hi, k - m - 1)  
    else:
        return select(lo, k)  

if __name__ == '__main__':
    seq = [3, 4, 1, 6, 3, 7, 9, 13, 93, 0, 100, 1, 2, 2, 3, 3, 2]
    print(select(seq, 0))
    print(select(seq, 1))

找到第n大的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 划分（基于主元 pivot），注意：非就地划分
def partition(seq):
     pi = seq[0]  # 挑选主元
     lo = [x for x in seq[1:] if x <= pi]  # 所有小的元素
     hi = [x for x in seq[1:] if x > pi]  # 所有大的元素
     return lo, pi, hi

# 查找第 k 小的元素
def select(seq, k):
     # 分解
     lo, pi, hi = partition(seq)
     m = len(hi)
     if m == k - 1:
          return pi  # 解决！
     elif m < k:
          return select(lo, k - m - 1)
     else:
         return select(hi, k) 
if __name__ == '__main__':
     seq = [3, 4, 1, 6, 3, 7, 9, 13, 93, 0, 100, 1, 2, 2, 3, 3, 2]
     print(select(seq, 1))
     print(select(seq, 2))

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
li = [100, 2, 89, 98, 23, 76, 38, 85, 12, 9, 4]


def quick_sort2(li):
    if len(li) < 2:
        return li
    tmp = li[0]
    left_list = [x for x in li[1:] if x < tmp]
    right_list = [x for x in li[1:] if x > tmp]

    return quick_sort2(left_list) + [tmp] + quick_sort2(right_list)


li = quick_sort2(li)
print(li)