分治

Divide and Conquer. 在之前读 Eric Roberts 先生所著的 Thinking Recursively 之后写过几句小总结,那本小书介绍了如何以递归的角度去看一些数据结构和算法,比如树和汉诺塔问题. 其中的三点, 也就是现在这篇文章需要总结的, 分治.

概念

算法导论_ 上是这么说用分治算法解决一个问题的:

Divide the problem into a number of subproblems that are smaller instances of the same problem.
Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner.
Combine the solutions to the subproblems into the solution for the original problem.

准确的来说,分治是一种思想,而不是某一个具体的算法,只要符合上述思想,先找到形式相同的子问题,然后依次解决子问题,再把子问题合起来,得到最终的结果的算法,都是分治.

实例

举个简单的例子,快排:

.. code:: python

def qsort(alist):
    length = len(alist)
    if length <= 1:
        return alist

    mid = length // 2
    less = list(filter(lambda x: x < alist[mid], alist))
    more = list(filter(lambda x: x > alist[mid], alist))
    return qsort(less) + [alist[mid]] + qsort(more)

首先我们找到一个pivot, 把小于他的放到左边, 把大于他的放到右边, 并且分别对左边和右边递归进行这个操作,然后把结果合起来,返回结果.

证明

证明递归算法的O复杂度方法有三种:

substitution method.

先猜测算法复杂度,再用数学证明.
recursion-tree method.

画出递归树,然后把每层复杂度相加.
master method.

根据公式计算(公式见 算法导论_ ).

实例

接下来我们拿最大子序列问题来练练手.

最大子序列问题: 有一串数字,找出其中和为最大的那一段.

对于这个问题,有暴力解法, 先for循环从左到右,再在for的里面从右到左for一遍,记住出现最大子序列的sum, left_index, right_index. 暴力解法的O一般都不低,这个例子是O(n^2).
分治解法,想到这个解法的关键点在于,最大子序列要么在中点(中间的那个值的index) 的左边,要么在右边,也有可能横跨中点,是左右加起来.但即使是在左边或者右边,也是在左边一部分的中点上(右边同理).所以这里的关键是建立 递归信任_ .这个解法的 O为O(nlgn). O(nlgn)解法_
是不是没有比O(nlgn)更低的算法了呢?不是,对于这个问题,还有更快的算法,就是先从左向右,累加,找到最大值的sum和right_index,然后再从左向右减,看是不是能找到更大的sum,并记录leftindex.这个算法最多只要扫描两遍,算法复杂度为O(n). O(n)解法

.. _算法导论: https://mitpress.mit.edu/books/introduction-algorithms .. _O(nlgn)解法: https://github.com/jiajunhuang/intro_to_algorithms/blob/master/chap4/max_subarray/maxsub.c .. _O(n)解法: https://github.com/jiajunhuang/intro_to_algorithms/blob/master/chap4/max_subarray/maxsub_linear.c .. _递归信任: ./2015_09_05-thinking_recursively.rst

分治

概念

实例

证明

实例

更多文章