分治策略的更多实例

分治策略的思想概述

分治策略即将问题不断拆分成更小的问题,再对一个足够小的问题进行简单的求解。

递归的基本步骤

  1. 分解 : 将问题划分为一些更小的问题,问题形式不变,但规模更小。
  2. 解决 : 递归的求解出子问题。如果子问题规模足够小则停止递归(该情况称为进入了基本情况,形象的可以想像为"触底"。
  3. 合并 : 将子问题的解组合成原问题的解。

递归策略的性能分析

递归策略性能的描述方法

我们常用递归式的方式来描述一个递归实例在运行时间上的性能
$$ T(n)=\begin{cases}
aT(\frac{n}{b}) + \theta(n) &n>1 \\
\theta(1) &n=1
\end{cases}$$
其中 a 是分解时产生的子问题的个数,每个子问题是原问题规模的$\frac{1}{b}$
当问题的规模足够小时(即n=1时)我们认为解决该问题只需要常数时间(其上界为一个常数)为$\theta(1)$。
所以对于归并排序 而言a=b=2。故其运行时间的描述为
$$ T(n)=\begin{cases}
2T(\frac{n}{2}) + \theta(n) &n>1 \\
\theta(1) &n=1
\end{cases}$$
对上式求解我们可以得到递归排序 的运行时间的渐近紧上确界为$\theta(n*\lg_2n)$

递归式的求解方法

此处介绍算法导论 中给出的三种求解方法\

  1. 代入法
  2. 递归树法
  3. 主方法 (主方法将会是求解的最常用的方法)

将会用归并排序 为例来介绍三种求解方法

代入法

即猜测一个界,然后用数学归纳法证明界的正确性。(类似于微积分中一阶非齐次线性微分方程 解的公式的推导)
使用代入法最好的情况是曾经遇见过很类似的递归式的形式,然后猜测二者解的形式类似


对于归并排序 我们猜测其解为$T(n)=O(n \log_2^n)$(不要问我怎么猜出来的)
然后我们来证明解的正确性.
我们需要证明
当$\exists N$使得$n>N$时$T(n)\geq cn\log_2^n$成立。
不证明n=1时的情况是因为因为当$N$很小时我们并不乎。(我们可以把基本情况设置为任意一个我们能够简单证明的数值),即将归纳证明中的基本情况与递归式中的基本情况区分开来

  • 首先观察当$N=2$(将N=2作为归纳证明的基本情况)时,$T(1)=1$从而推导出$T(2)=4,T(3)=5$
  • 基本情况讨论完成后,我们只需要寻找$c \geq 1$使得$T(n) \leq cn \log_2^n$,对于我们已经讨论过的基本情况
    显然$\forall c\geq2$都能使$T(2)\leq 2c\log_2^2$和$T(3)\leq3c\log_2^3$成立。所以基本情况$n=2,n=3$成立。
  • 所以可以推出我们的猜测时正确,即为$T(n)=O(n \log_2^n)$

递归树法

将递归式转化为树状结构,其节点 为递归产生的代价,累加各层节点 来求解递归式。


递归树图示


主方法

  • 主方法可求解形如$T(n) = aT(\frac{n}{b})+f(n)$的界,其中$a \geqq 1,b>1,f(n)已知且为渐近正函数$(n足够大时,函数值均为正的函数)
  • $T(n) = aT(\frac{n}{b})+f(n)$该式子描述了"生成a个子问题,每个子问题为原问题规模的$\frac{1}{b}$,解决和合并产生的代价为$f(n)$"
  • 值得注意的是$\frac{n}{b}$并不一定是整数,但在n足够大时,$\frac{n}{b}$与$[\frac{n}{b}]$并不会影响递归式的渐进性质,所以这里我们都将$\frac{n}{b}$当作$[\frac{n}{b}]$

使用主方法只需要记忆以下三种情况,套用公式即可

  1. 若$\exists\epsilon>0$使$f(n)=O(n^{\log_b^{a-\epsilon}})$则$T(n) = \theta(n^{\log_b^a})$
  2. 若$f(n)=\theta(n^{\log_b^a})$,则$T(n)=\theta(n^{\log_b^a}*\log_2^n)$
  3. 若$\exists\epsilon>0$使$f(n)=\Omega(n^{\log_b^{a+\epsilon}})$,且对于某个常数$c>1,\exists{N}>0$使得当$n>N$时,有$af(\frac{n}{b})\leq{c*f(n)}$,则$T(n)=\theta(f(n))$

主方法来分析归并排序
$$ T(n)=\begin{cases}
2T(\frac{n}{2}) + \theta(n) &n>1\\
\theta(1) &n=1
\end{cases}$$
仅考虑$n>1$的情况,用主方法的形式对应上式$a=2,b=2,f(n)=\theta(n)$
显然此时满足情况2 ,故$T(n) =\theta(n\log_2^n)$

主方法的证明将会在有空的时候给出( 写公式太恶心心了),而且主方法的证明篇幅足够再水一周的博客了hhhhhh。


碎碎念

又水了一周hhhhhh
但是其实分析性能还是很有意思的一个事情(才没有233)