算法从入门到“放弃”（2）- 分而治之和解决循环

本文提炼

分而治之（Divide - and - Conquer）和3种解决循环的方法。

分而治之 Divide - and - Conquer

分而治之，简单来讲，就是三步：

1. 分开 Divide，把问题分成一个个小问题，这些小问题是一个个小实例
2. 解决 Conquer，用递归把一个个小问题解决掉。如果一个个小问题很少，那就直接把它们解决掉，不需要用到递归了
3. 合并 Combine，把一个个小问题的答案合并起来组成原问题的答案

当一个个小问题足够多的时候，我们就称之为递归情况（recursive case）；当一个个小问题变少了，不再需要用到递归的时候，我们称这个递归“到底”了，到达了基础情况（base case）。
所以，当我们用递归解决一个问题的时候，我们会在递归的每一个水平都带入这三步。

循环 Recurrences

那什么是循环呢？

按照书本上的解释，循环就是一个描述了按照更小的输入得到值的函数的等式或不等式。（an equation or inequality that describes a function on terms of its value on smaller inputs）

我个人的理解就是，任何重复执行一个函数的过程，就都是循环。就像书本的解释，最小的输入经过一个函数得到一个结果/值，我们再用这个值当做输入经过同一个函数得到值，再用这个值经过同一个函数。。。。。直到达到我们在第一部分提到的基础情况，这时候，循环就结束了。

这就是一个循环

3种解决循环的方法

• 替换法 substitution method，首先猜一个范围，接着用数学归纳法证明我们的猜想是正确的。

举个例子（例子来源），有下面这个循环，我们需要确定上范围 (upper bound)。

就像上图所写，先是猜想，T(n) <= cnlog(n)；接着是证明，第一步是验证基础情况，n=1；正确之后是第二步，归纳过程，对T(n) 和cnlog(n)里所有的n 用n/2 代替。
为什么用n/2 ？我们要假设这个范围是对任何小于n 的正数m 有效，大部分情况直接使用m = n/2 了。
为什么在这里不用n-1 呢？因为我们的猜想里有log 函数，想想log 函数在x = 1 临界点左右两边正负不同的情况（个人理解，若不对或则是别的原因，请在评论区指明，谢谢！）。
一直觉得这个办法像玄学，怎么猜这个范围，需要你做很多算法题得出的经验和自己的想象力。但是凭借下面将要介绍的另外一种方法，猜想也就变得不那么云里雾里。

• 递归树方法 recursion-tree method，把循环转换成每个节点代表递归中不同水平里产生的成本的树。我们再用方法把边界的和求出，就可以解决循环了。
  递归树可以帮助我们想出一个好的猜想，然后我们就可以用替换法来验证。举个例子（例子来源），下面的函数画成递归树。

首先我们看下这棵数有多高呢？因为这棵树的每个节点的尺寸都是上一个的1/2，当我们最终到达底端，底端(在深度i）的节点尺寸是n/(2^i)。也就是说，当n=1，节点的尺寸是n/(2^i) = 1，换句话说，当i = log2(n)。所以这棵树的高度是log2(n)。

接着，我们来判断这棵树每个水平消耗的成本。从图中可以看出，每个水平的节点数量是上一水平的8倍，所以在深度i，节点数量是8^i。因为每个小问题的尺寸都是上一级的1/2，所以每个深度为i (i=0,1,2,3…log2(n-1))的节点，消耗的成本是(n/2^(i))^2. 现在求每个深度为i 的水平上所有节点的成本，8^i* (n/2^(i))^2 = (8/4)* n^2 = 2n^2. 而在底层，当深度为log2(n), 我们有8^(log2(n)) = n^(log2(8)) = n^3 个节点，每个都消耗成本T(1) = 1，所以总消耗是n^3.

然后就是计算整棵树所有水平消耗的成本了。就是上图中最后一个等式。我们将它整理一下，

因此我们有了一个猜想，T(n) = O(n^3)，然后我们就可以用替换法来验证了。XD

• 主方法 master method，提供了类似下面格式 T(n) = aT(n/b) + f(n) 的循环的范围。格式中a>=1, b>1，f(n) 是一个已知函数。

整理完前两种方法，第三种即将要说明的方法真的是太简便了。这就像是提供给了我们菜谱，只要材料对了，跟着步骤走肯定就能做出一道美味可口的菜。

但是也有限制，除了上面提到的格式，我们还得记住三种情况：
我们在格式中提到的n/b 即可以代表floor n/b 也可以代表 ceil n/b. (地板功能就是我们输入一个实数x，它给出小于或等于x 的最大整数。类似地，天花板函数就是将x 转换到大于或等于x 的最小整数。例如，floor(2.4)=2, ceil(2.4)=3)

1. 如果存在大于0的x 满足f(n) = O(n^(logb(a) - x) ，也就是说f(n) 小于n^(logb(a) 函数，那么T(n) = Ө(n^(logb(a)).
2. 如果f(n) = Ө(n^(logb(a))，那么T(n) = Ө(n^(logb(a)* lg(n)) = Ө(n^(f(n)* lg(n)) .
3. 如果存在大于0的x 满足f(n) = Ω(n^(logb(a) + x) ，也就是说f(n) 大于n^(logb(a) 函数，而且同时满足“如果存在小于1的c，对于所有的足够大的n，a* f(n/b) <= c* f(n)”的条件，那么T(n) = Ө(f(n)).

针对这三种情况，书本给出了对应的三个例子。

这三种方法里我最喜欢的就是主方法，只要循环符合它的特定形式，直接公式走起，简洁明了。

补充 - 循环(loop), 递归(recursion), 遍历(traversal), 迭代(iterate)之间的区别

在查阅网上资料的时候，发现了这个有趣的区别总结，就作为补充放在这了。来源：编程中，循环、迭代、遍历和递归之间的区别，侵权删。

• 循环(loop) - 最基础的概念, 所有重复的行为。大部分的递归, 遍历, 迭代, 都是循环。
• 递归(recursion) - 在函数内调用自身, 将复杂情况逐步转化成基本情况；经典的解释就是，什么是递归，参见递归。
• (数学)迭代(iterate) - 在多次循环中逐步接近结果
• (编程)迭代(iterate) - 按顺序访问线性结构(数组, 队列)中的每一项，在很多编程语言中表现为foreach语句
• 遍历(traversal) - 按规则访问非线性结构(树, 图)中的每一项

在接下来的几篇文章中，将着重讲的是各种排序算法。

文章来源

来自2018年写的系列文章：https://zhuanlan.zhihu.com/p/40179286。