算法的复杂度表示及主定理
算法的复杂度表示
$f(n), g(n)$ 是 $\mathbb{N}^{+} \to \mathbb{R}^+$ 的函数。使用 $O$ 符号描述一个函数的 上界($f(n) = O(g(n))$。即:$\exists c, n_{0}$,使得 $\forall n \geq n_{0}, 0 \leq f(n) \leq c \cdot g(n)$),使用 $\Omega$ 符号描述一个函数的 下界($f(n) = \Omega (g(n))$)。即:$\exists c, n_{0}$,使得 $\forall n \geq n_{0}, 0 \leq c \cdot g(n) \leq f(n)$)。如果 $f(n) = O(g(n))$ 且 $f(n) = \Omega (g(n))$,使用 $\Theta$ 符号表示 $f(n) = \Theta (g(n))$。
主定理(Master Theorem)
Master Theorem 递推关系式:$\forall n > b, T_{n} = aT(\frac {n}{b}) + f(n)$($a > 0, b \geq 1$)。
主定理:
$$
T(n)= \begin {cases}
\Theta (n^{\log_b a}) & f(n) = O(n^{\log_b a-\epsilon}) \\
\Theta (f(n)) & f(n) = \Omega (n^{\log_b a + \epsilon}) \\
\Theta (n^{\log_b a} \log^{k + 1} n) & f(n) = \Theta (n^{\log_b a} \log^{k} n, k \geq 0)
\end {cases}
$$
情况二正则条件:$af(n / b) \leq cf(n)$($k \leq 1 $ 并且 $n$ 足够大)
证明:将规模为 $n$ 的问题,分解为 $a$ 个规模为 $(\frac {n}{b})$ 的问题,然后一次合并,知道合并到最高层。每一次合并子问题,都需要花费 $f(n)$ 的时间。
对于第 $0$ 层(最高层),合并子问题需要花费 $f(n)$ 的时间;对于第一层(第一次划分出来的子问题),共有 $a$ 个子问题,每个子问题合并需要花费 $f(\frac {n}{b})$ 的时间所以总共要花费 $a(\frac{n}{b})$ 的时间。层层递推,可以写出类推树如下:
这棵树高度为 $\log_{b}n$,共有 $n^{\log_{b}a}$(实际是 $a ^ {\log_{b}n}$,$n^{\log_{b} a} = b ^ {\log_{b}n \cdot log_{b}a}=n^{\log_{b}a}$)个叶子,从而 $T(n) = \Theta (n ^ {\log_{b} a}) + g(n)$,其中 $g(n) = \sum_{j = 0}^{\log_{b} {n - 1}}a^{j}f(n/b^{j})$。
令 $f(n/b^{j}) = O((\frac {n}{b^{j}}) ^ d) = c \cdot (\frac {n}{b^{j}}) ^ d$($d \geq 0$),可以推出如下:
$$
\begin {aligned}
g(n) = &a^{0}f(\frac {n}{b^{0}}) + a^{1}f(\frac {n}{b^{1}}) + \cdots + a^{\log_{b}{n - 1}}f(\frac {n}{b^{\log_{b}{n - 1}}}) \\
= & a^{0} \cdot c(\frac {n}{b^{0}})^d + a^{1} \cdot c(\frac {n}{b^{1}})^d + \cdots + a^{\log_{b}{n - 1}} \cdot c(\frac {n}{b^{\log_{b}{n - 1}}})^d \\
= & c \cdot n ^ {d}[1 + (\frac{a}{b^{d}}) + (\frac {a}{b^{d}})^2 + \cdots + (\frac {a}{b^{d}})^{\log_{b}{n - 1}}]
\end{aligned}
$$
按照等比数列求和公式,分三种情况讨论:
情况1:公比大于 $1$,$a > b^{d}$,等比数列中不断增大,只看其最大值,因此 $g(n) = n^{d} \cdot (\frac{a}{b^{d}})^{\log_{b}n} = n^{d} \cdot (\frac {a^{\log_{b}n}}{(b^{\log_{b}n})^d}) = a^{\log_{b}n} = n^{\log_b{a}}$。
情况2:公比小于 $1$,$a < b^{d}$,等比数列中不断减小,因此 $g(n) = \Theta(f(n))$。
情况3:公比等于 $1$,$a = b^{d}$,$f(n) = \Theta(n^{log_{b}a})$,因此 $g(n) = O(n^{\log_{b}a}logn)$。$T(n)$ 的结果可在 $g(n)$ 得出后显然得到。
举例如何应用:
例如 $T(n) = 3 T(\frac{n}{2}) + 2n$,那么 $a = 3, b = 2, d = 1$,满足情况一,所以 $T(n) = \Theta(n^{log_{2}3})= O(n^{2})$。
例如 $T(n) = T(\frac {n}{2}) + 1$,那么 $a = 1, b = 2, d = 0, k = 0$,根据情况二的正则条件,不满足 $n$ 足够大,所以满足情况三,所以 $T(n) = \Theta (\log{n})$。
例如 $T(n) = T(\frac {n}{2}) + \log_{2}{n}$,那么 $a = 1, b = 2, n ^ {d} = log_{2}n, k = 1$,满足情况三,所以 $T(n) = \Theta (log^{2}n)$。
lcx巨佬%%%