9.分治与递归

介绍如题的内容。

汉诺塔

汉诺塔是颇为出名的游戏，有三根柱子，一开始一根柱子上有 个圆盘，从上到下越来越大。每次移动一个圆盘，必须先移动最上面的圆盘，圆盘必须移动到比自己小的圆盘上方。经过多少步才能把所有圆盘移动到另一个柱子上？假设是 步。

经典的做法是递归。要移动 个圆盘，可以先移动前 个圆盘到另一根柱子上，把最底下的圆盘移动到剩下的柱子，再把 个圆盘移动到目标柱子上。这样每个过程都等价成更小数值圆盘的移动。也就有：

实际上这也就是我们能做到的最好的办法了。我们总要移动最后一个圆盘，在这时，其他圆盘一定在剩下的柱子上，也就是说此时的步数 。那么移动也至少一步，最后也一样，至少是 ，因此 ，那么：

如何求解呢，高中我们学过待定系数，刷题的功劳就是，由于过分的熟悉，我们会机械地两边加一构造等比数列。但一般地呢，如果我们没见过呢？

猜测与验证是非常常见的数学方法。猜到答案之后，利用归纳法证明，是一个很不错的路径。我们算出前几项，不难发现是 ，自然会猜测通项是 ，那么就可以利用归纳法证明。

如果这时候还注意不出来，可以直接一层一层地套递推式，容易观察到这样的结构：

其中 也就是 ，那么利用等比数列求和我们同样能得到结果。

归并排序(merge sort)

给 个数 排序，方便起见令 。分成两步：

• 给 和 排序
• 合并两边，比较两边最小值即可

设 是最差情况下归并排序需要的比较次数。

合并中，最差情况下我们比较 次。分别排序则是 。那么：

这个式子就没法一眼顶针了。通常我们算出几项观察。前几项会是 看起来不好猜，那么我们尝试代入递推式。

再次代入就得到

如果忍住化简前面的式子，这样总能猜到了（

最后，在我们美丽的假设下，令 ，此时最后那个就是 ，就得到

几乎是线性的，比挨个比较快上不少。

比较发现：

二者形式相似但差别巨大，就在于 里边的不同。

一般地不是 的幂次的情形，并稍微改改递推，我们变成 。代入 试试：，那么通项会是 吗，我们用加强的归纳法尝试：

[!归纳] 奠基步： ，成立。

归纳步：假设 ，，利用假设得到 ，尽管不知道 的奇偶性，但是 总会是 ，那么 也成立。

那么利用归纳公理就得到原命题成立。

那么也就是说 ，从 到 ，对数就消失了。

之前我们总是能通过猜和代入递推式解决，但是并不总是那么美妙。

这如果进行代入，就是大工程了（

Akra-Bazzi 定理

形如下式的递归方程：

• ：子问题的系数（如你图中 前面的 ）。

• ：规模缩减比例（如 和 ）。

• ：合并开销，必须是多项式，而且要求 。

• ：微小的扰动（比如之前的取整符号 ），要求 。

第一步：求出关键指数 这是最核心的一步。你需要找到一个 ，使得下列等式成立：

这个 决定了递归树中“叶子节点”的生长速度。

第二步：代入公式

一旦算出 ，直接套用这个积分公式：

据教授说，这个式子通过猜测得到（ 如果你愿意，可以尝试用归纳法验证，但有些 。

我们尝试用用：，这个归并排序的递推式， ， 就能让 。那么利用上述定理：

积分只要拆开就行，是容易的，最后也就得到

这并不很能显示定理的强大，我们看这个 :

运用定理，我们要找到 使得：

幸运的是 恰好符合方程，那么就有：

看起来可怕的递推变成了无脑的计算。但是 未必总是那么漂亮，例如：

我们就要考虑：

就不是整数了。 计算 ，会发现左侧比 小，说明 ，同样我们发现 。但好处是，我们直接看积分：

积分那项却很简单：

出来一个 ，由于 ，可以扔掉，就得到：

我们并不需要知道具体的 。实际上这是一个定理：

可以类似上方地证明。这样就十分方便了。