Master Theorem与时间复杂度分析

· · 个人记录

虽然很不想写这玩意儿。。。

因为找不到一些特别系统的证明之类的，，写的东西也很零散。。。

首先认识这几个符号： O,\Theta,\Omega ，它们分别表示时间复杂度最坏情况的上界，确界，下界。然后还有一些不太常见的符号如 o,\omega ，类似于 O,\Omega ，但表示的时间复杂度是这个算法到达不了的，有点像是大于号小于号与大于等于小于等于号的区别。

因此有些事情是正确的：

T(n)=\Theta(n^2)=O(n^3)

然后这玩意的分析基本只在初赛会考，，平常了解个大概就可以了。。。所以大多数人都不分 O 与 \Theta ，因为从算法实现的角度来讲，这两个东西的意义是差不多的。。。剩下的符号基本就没有在初赛出现过。。。

以前我对时间复杂度的分析基本建立在程序的运行上，大概是凭感觉搞到了现在。。。导致我初赛的时间复杂度分析基本是靠拆式子之类的奇技淫巧做的。。。

主定理 Master Theorem。

从做题的角度来说，这个东西背下来大部分题就能做了。。。

但是还是写一个奇怪的证明罢。。

我们一般会把递归公式写成这样的形式：

T(n)=aT(\dfrac{n}{b})+\Theta(n^d)

然后我们来拆式子，就能得到这样一个东西：

T(n)=\sum_{i=0}^{\log_b n}a^i\Theta((\dfrac{n}{b^i})^d)

稍微整理一下就能得到：

T(n)=\sum_{i=0}^{\log_b n}\Theta(n^d)(\dfrac{a}{b^d})^i

根据等比数列的求和公式：

  1. 若 \dfrac{a}{b^d}<1 。来一个比较初中的推导。设 x=\log_b a 则 a=b^x ，那么就有 \dfrac{b^x}{b^d}<1 ，可以得到 x<d ，即 \log_b a<d 。此时，算法复杂度由数列的第一项决定，就是 \Theta(n^d) 。这也解释了主定理的第三条。

  2. 若 \dfrac{a}{b^d}>1 。同理，易证 \log_b a>d 。那么时间复杂度由最后一项决定。然后来一个不太初中的推导：

\begin{aligned}T(n)&=\Theta(n^d)(\dfrac{a}{b^d})^{\log_b n}\\&=\Theta(n^d)\dfrac{a^{\log_b n}}{(b^{\log_b n})^d}\\&=\Theta(n^d)\dfrac{a^{\log_b n}}{n^d}\\&=\Theta(a^{\log_b n})\\&=\Theta(a^{\frac{\log_a n}{\log_a b}})\\&=\Theta((a^{\log_a n})^{\frac{1}{\log_a b}})\\&=\Theta(n^{\frac{1}{\log_a b}})\\&=\Theta(n^{\log_b a})\end{aligned}

从而解释了主定理的第一条。

  1. 若 \dfrac{a}{b^d}=1 。那么上式变得简单了起来：
T(n)=\sum_{i=0}^{\log_bn}\Theta(n^d)=\Theta(n^d\log_b n)

从而解释了主定理的第二条。

没了。

当然如果你足够 nb，可以直接把这个东西积分近似，然后定积分大概两三步就能把主定理推出来。

实际上定积分近似是非常强大的工具，因为它能处理的东西比一般的主定理要多。。。