算法入门(1) 算法分析 - Li Jiaheng's blog

常见符号#

严格范围： $\Theta(\cdot)$ （as tight as we can，tight bound）， $T(n)=\Theta(f(n))$ 意味着 $T(n)=\Omega(f(n)),T(n)=O(f(n))$ .
不大于（上界）： $O(\cdot)$ .
下界（不严谨）： $\Omega(\cdot)$ ， $f(n)=\Omega(g(n))$ 表明，存在一个常数 c，存在一个 n0，使得对于所有 n>n0，有 $f(n)>c\times g(n)$ . 所以虽说是下界，但不是数学上严格定义的下界，首先隐去了常数系数，其次要 n 足够大 (large enough)

上面的 $\Theta, O, \Omega$ 严格来说是集合，上面的 $=$ 可以解释为 $\in$ 。

在 n 足够大， $\Theta, O, \Omega$ 就是同级无穷大、上界（高级无穷大）、下界（低级无穷大）。应当注意， $\log_b n \sim \log_2n=\log n$ for $\log_bn=\frac{\log_2n}{\log_2b}$

简单结论#

分治法结论：

\begin{aligned} T(n)&=T(\frac{n}{2})+\Theta(n) \\ &=\Theta(n\log n) \end{aligned}

通用的递归法 $T(n) = cT(\frac{n}{b})+f(n)$ ：
将 n 根据树状结构不断细分下去，每个节点（假设其值是k)都有自己的 f(k)，一直到最后叶子的 f(1).

\begin{aligned} T(n) &\lt f(n)+bf(n/b)+b^2f(n/b^2)+\dots \\ &<(1+b+b^2+\dots+b^{log_bn})O(f(n)) \\ &<\frac{1-bn}{1-b}O(f(n)) \\ &<\frac{b}{b-1}nO(f(n)) \end{aligned}

注意，这个放缩放得太宽了。
Master定理

\begin{aligned} T(n) &= aT(n/b)+O(n^d) \\ T(n) &= a(aT(n/b^2)+O((n/b)^d))+O(n^d) \\ &\dots \\ T(n) &= a^{log_bn}+\sum_{i=0}^{log_bn}a^iO((n/b^i)^d) \\ T(n) &= n^{log_ba} + O(n^d)\sum_{i=0}^{log_bn}\frac{a^i}{b^{id}} \end{aligned}

更详细的推导，在红色小本上。
结果是：

\begin{aligned} T(n) = \begin{cases} O(n^d), \quad d>log_ba \\ O(n^dlog_n), \quad d=log_ba \\ O(n^{log_ba}), \quad d<log_ba \end{cases} \end{aligned}

只用再证下界。递归成树出来的结果一般是 tight bound, 可以写成 $\Theta$

简单的上界 $O(\cdot)$ 结论

调和级数： $\sum_{i=1}^n\frac{1}{i}=O(\log n)$ (将分子放缩为2的幂)。