【算法点滴】分治策略小结

分治策略介绍

分治策略可概括为以下步骤：

1. 分解（Divide）：将问题分解为若干个小的子问题。每个子问题与大问题同型，但规模小。
2. 解决（Conquer）：递归解决子问题。（递归是彰显分治优势的放大器，仅仅进行一次分治策略，也许改善的效果很小，但递归的进行分解下去，把问题分解到微不足道的境地，子问题的解即可用常数时间求得）
3. 合并（Combine）：将子问题的解答合并，获得大问题的解答。

在分而治之的策略下，所有工作被设定为分解部分、递归部分和合并部分。而整体的时间复杂度由这三部分的时间复杂度之和构成。
由于不断递归，最后的子问题变得极为简单，以至于其时间复杂度在整个策略上的比重微乎其微。因此，分而治之策略的真正成本实际在分解与合并两个部分上，即问题在需要分解多少次，每次分解的子问题数是多少？需要合并多少次，每次分解与合并需要的时间是多少？

递归表达式与递归树

一般来说，分支策略将一个大的复杂的问题划分为a个同型的子问题，这些子问题的规模是n/b。如果一直递归分解下去，可得到描述算法时间复杂度的递归表达式：
$$T(n) = aT(n/b)+f(n)$$
这里，b是每次分解时问题规模减小的因子，a是每次分解时产生的子问题个数，f(n)是分解与合并a个大小为n/b的子问题的成本。
而递归树是抽象的递归表达式具体化的图形表示，它给出的是一个算法递归执行的成本模型。该模型以输入规模为n开始，一层一层分解，直到输入规模变为1为止。

recursion tree

替换法

替换法是先才某个界存在，再用数学归纳法证明正确性，通过解决表达式中的常数c来验证答案。
举例来说明，比如我们需要用替换法来证明T(n) = T(n/4)+T(n/2)+n^{2的解为$$Θ(n}2)$$，即分别证明$$T(n)=O(n^{2)$$和$$T(n)=Ω(n}2)$$。

替换法

主定理

定义

主方法给出求解形如T(n) = aT(n/b) + f(n)的递归表达式的定理性方法，这里常数a>=1，b>1，f(n)是一个渐进趋正的函数（存在n0，当n>n0，有f(n)>0）。
递归式T(n) = aT(n/b) + f(n)描述了将规模为n的问题划分为a个子问题的算法的运行时间，每个子问题规模为n/b，a和b是正整数。a个子问题被分别递归地求解，时间各为T(n/b)。划分原问题和合并答案的代价由函数f(n)描述。
*主定理：设a>=1，b>1为常数，f(n)是一个函数，T(n)由递归式T(n) = aT(n/b) + f(n)对非负整数定义。那么T(n)可能有如下的渐进界，

master method

主定理的形象解释

递归式展开

然后给出递归式T(n) = aT(n/b) + f(n)的递归树图形：

主定理思想

case 1情况下，递归树的每层成本从根向下呈几何级数增长，成本在叶节点一层达到最高，即最后一次递归是整个过程中成本最高的一次，故其占主导地位。所以递归分治的总成本在渐进趋势上和叶子层的成本一样。
case 2情况下，递归树每层的成本在渐进趋势上一样，即每层都是n^logb(a)。由于有logb(n)层，因此总成本为每层的成本乘以logb(n)。
case 3情况下，递归树每层成本呈几何级数递减，树根一层的成本占主导地位。因此，总成本就是树根层的成本。

主定理的证明

case 1由所有叶结点的代价决定

case1

case 2 树的代价均匀地分布在各层上

case2

case 3 由根结点的代价决定

case3

特别说明：f代表的是分治策略中的分解（成子问题）和合并（子问题）的成本。由于f(n)的渐进增长趋势>Θ(n^logb(a))，所以该分治策略的分解和合并成本高于子问题的解决成本。而如果在这种情况要获得解，分解和合并的成本应该逐级下降；否则，分解和合并成本随着分解的推进将呈现发散趋势，这样总成本有可能不会收敛。那么这种分治策略就显得没有意义了。
而如果分解与合并成本逐级下降，则意味着函数f满足af(n/b)<=cf(n)，其中c<1。因此，解为T(n)=Θ(f(n))。