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}\]