分治策略与主定理

== 支配理论 ==
假设有递归关系式 $T(n) = a T\left(\frac{n}{b}\right) + f(n)$,其中$ a \geq 1 \mbox{, } b > 1$

其中,n 为问题规模, a 为递归的子问题数量,$\frac{n}{b}$ 为每个子问题的规模(假设每个子问题的规模基本一样),f(n) 为递归以外进行的计算工作。

=== 情形一 ===
如果存在常数$ \epsilon > 0 $,有

$ f(n) = O\left( n^{\log_b (a) - \epsilon} \right)$(可不严谨地视作多项式地小于)

则: $ T(n) = \Theta\left( n^{\log_b a} \right) $

=== 情形二 ===
如果存在常数$ \epsilon\ge0 $,有: $f(n) = \Theta\left( n^{\log_b a} \log^{\epsilon} n \right)$

则: $T(n) = \Theta\left( n^{\log_b a} \log^{\epsilon+1} n \right) $

=== 情形三 ===
如果存在常数$ \epsilon > 0 $,有: $ f(n) = \Omega\left( n^{\log_b (a) + \epsilon} \right) $(多项式地大于)

同时存在常数$c < 1$以及充分大的$n$,满足:$a f\left( \frac{n}{b} \right) \le c f(n)$

则:$T\left(n \right) = \Theta \left(f \left(n \right) \right)$

== 常用算法中的应用 ==

算法 递归关系式 运算时间 备注
二分搜索 $ T(n) = T\left(\frac{n}{2}\right) + \Theta(1) $ $\Theta(\log n)$ 情形二($\epsilon=0$)
二叉树遍历 $T(n) = 2 T\left(\frac{n}{2}\right) + \Theta(1) $ $\Theta(n)$ 情形一
最佳排序矩阵搜索(已排好序的二维矩阵) $T(n) = 2 T\left(\frac{n}{2}\right) + O(\log n)$
归并排序 $T(n) = 2 T\left(\frac{n}{2}\right) + \Theta(n)$ $\Theta(n\log n)$ 情形二($\epsilon=0$)
Donate
  • Copyright: Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.

请我喝杯咖啡吧~

支付宝
微信