分治

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, leftindex, rightindex. 暴力解法的O一般都不低,这个例子 是O(n^2).

  • 分治解法,想到这个解法的关键点在于,最大子序列要么在中点(中间的那个值的index) 的左边,要么在右边,也有可能横跨中点,是左右加起来.但即使是在左边或者右边,也是 在左边一部分的中点上(右边同理).所以这里的关键是建立 递归信任_ .这个解法的 O为O(nlgn). O(nlgn)解法_

  • 是不是没有比O(nlgn)更低的算法了呢?不是,对于这个问题,还有更快的算法,就是先从 左向右,累加,找到最大值的sum和rightindex,然后再从左向右减,看是不是能找到更大 的sum,并记录leftindex.这个算法最多只要扫描两遍,算法复杂度为O(n). O(n)解法_

.. _算法导论: https://mitpress.mit.edu/books/introduction-algorithms .. O(nlgn)解法: https://github.com/jiajunhuang/introtoalgorithms/blob/master/chap4/maxsubarray/maxsub.c .. O(n)解法: https://github.com/jiajunhuang/introtoalgorithms/blob/master/chap4/maxsubarray/maxsub_linear.c .. 递归信任: ./20150905-thinkingrecursively.rst


更多文章
  • Python dataclass 源码阅读与分析
  • gRPC-gateway 源码阅读与分析
  • 如何阅读源代码
  • 我心目中的配置中心应该怎么做?
  • 设计一个HTTP网关
  • 设计一个分布式块存储
  • Linux低电量自动关机
  • CGO简明教程
  • 求值策略:Applicative Order vs Normal Order
  • High Performance MySQL阅读笔记
  • MySQL EXPLAIN中的filesort是什么?
  • 数据库索引设计与优化
  • 如何调试?
  • Docker CE 18.03源码阅读与分析
  • 容器时代的日志处理