1. 算法复杂度与主定理

递归算法的复杂性分析方法：代入法、递归树、主定理。这里只讨论主定理方法。

主定理方法应用于如下的递归形式：

\[T(n) = aT(\frac{n}{b}) + f(n).\]

其中，\(a \geqslant 1,\ b\geqslant 1\) ，\(f\) 是渐进正的。

1.1. 渐进分析

假设对于所有 \(n\) ，满足 \(f(n) \geqslant 0,\ g(n) \geqslant 0\) 。

• 渐进上界 \(\mathcal{O}\)

  \[\mathcal{O}(g(n)) = \{ f(n) | \text{存在正常数} c \text{和} n_0 \text{使得对所有} n \geqslant n_0 \text{有：} 0 \leqslant f(n) \leqslant cg(n) \}\]

• 渐进下界 \(\Omega\)

  \[\Omega(g(n)) = \{ f(n) | \text{存在正常数} c \text{和} n_0 \text{使得对所有} n \geqslant n_0 \text{有：} 0 \leqslant cg(n) \leqslant f(n) \}\]

• 渐进近界 \(\Theta\)

  \[\Theta(g(n)) = \{ f(n) | \text{存在正常数} c_1,\ c_2 \text{和} n_0 \text{使得对所有} n \geqslant n_0 \text{有：} c_1g(n) \leqslant f(n) \leqslant c_2g(n) \}\]

定理：

\[\Theta(g(n)) = \mathcal{O}(g(n)) \cap \Omega(g(n))\]

1.2. 主定理

需要比较 \(f(n)\) 和 \(n^{\log_b a}\) 。

• \(f(n) = \mathcal{O}(n^{\log_b a - \epsilon})\) ： \(f(n)\) 的增长速度比 \(n^{\log_b a}\) 慢一个 \(n^{\epsilon}\) 因子。

  \[T(n) = \Theta (n^{\log_b a})\]

• \(f(n) = \Theta (n^{\log_b a} \log^k n)\) ： \(f(n)\) 与 \(n^{\log_b a} \log^k n\) 具有相似的增长速度。

  \[T(n) = \Theta (n^{\log_b a} \log^{k+1} n)\]

• \(f(n) = \Omega (n^{\log_b a + \epsilon})\) ： \(f(n)\) 的增长速度比 \(n^{\log_b a}\) 快一个 \(n^{\epsilon}\) 因子，且满足 \(af(\frac{n}{b}) \leqslant cf(n),\ 0 < c < 1\) 。

  \[T(n) = \Theta (f(n))\]

例子：

\[\begin{split}T(n) = 4T(\frac{n}{2}) + n & \rightarrow &\ \epsilon = 1,\ T(n) = \Theta (n^2) \\ T(n) = 4T(\frac{n}{2}) + n^2 & \rightarrow &\ k=0,\ T(n) = \Theta (n^2 \log n) \\ T(n) = 4T(\frac{n}{2}) + n^3 & \rightarrow &\ \epsilon = 1,\ c=\frac{1}{2},\ T(n) = \Theta (n^3)\end{split}\]