分治 - Jiajun的编程随想

首页

/

友情链接

/

我的Github

/

关于我


分治

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

概念

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

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

实例

举个简单的例子,快排:

.. 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复杂度方法有三种:

实例

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

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

.. 算法导论: 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