一、渐近记号

本节定义一些基本函数，用于描述时间复杂度。

1.1 \(\quad\) 渐进记号、函数与运行时间

1.1.1 \(\quad\) \(\Theta\) 记号

我们使用 \(\Theta\) 记号描述函数的渐近紧确界。

形式化地， \(\Theta (g(n))=\{f(n):\exists c_1,c_2,n_0:\forall n\ge n_0,0\le c_1g(n)\le f(n)\le c_2g(n) \}\)。

其中，冒号意为“使得”。

也就是说，存在常量 \(c_1,c_2,n_0\)，可以将 \(f(n)\) 夹入 \(c_1g(n)\) 和 \(c_2(n)\) 中。\(\Theta(g(n))\) 要求每个成员 \(f(n)\in \Theta(g(n))\) 渐近非负。

我们通常使用 \(\Theta(1)\) 表示常量或某个变量的常量函数。

1.1.2 \(\quad\) \(O\) 记号

当函数只有一个渐近上界时，使用 \(O\) 记号。

形式化地， \(O (g(n))=\{f(n):\exists c,n_0:\forall n\ge n_0,0\le f(n)\le cg(n) \}\)。

使用 \(O\) 记号描述上界，我们常常可以检查算法的总体结构来描述算法运行的时间，如循环嵌套等，这里不再展开。

1.1.3 \(\quad\) \(\Omega\) 记号

\(\Omega\) 记号提供了函数的渐近下界。

形式化地，\(\Omega (g(n))=\{f(n):\exists c,n_0:\forall n\ge n_0,0\le cg(n)\le f(n)\}\)。

我们不难有如下定理：

定理 \(\quad\) 对于任意两个函数 \(f(n),g(n)\)，我们有 \(f(n)=\Theta(g(n))\)，当且仅当 \(f(n)=O(g(n))\) 且 \(f(n)=\Omega(g(n))\)。

1.1.4 \(\quad\) \(o\) 记号

前面的 \(O\) 记号描述的渐近上界，我们使用 \(o\) 记号来描述一个非渐近紧确的上界，如 \(2n=o(n^2)\) 而 \(2n^2\not=o(n^2)\)。

形式化地，\(o (g(n))=\{f(n):\forall c>0,\exists n_0>0:\forall n\ge n_0, 0\le f(n) < cg(n) \}\)。

直观上，在 \(o\) 记号中，当 \(n\rightarrow + \infty\)，函数\(f(n)\) 相对于 \(g(n)\) 来说变得微不足道了。

1.1.5 \(\quad\) \(\omega\) 记号

我们使用 \(\omega\) 记号描述一个非渐近紧确的下界。

形式化地，\(\omega (g(n))=\{f(n):\forall c>0,\exists n_0>0:\forall n\ge n_0, 0\le cg(n) < f(n) \}\)。

1.2 \(\quad\) 渐近函数的性质

我们令 \(f(n),g(n)\) 渐近为正。

渐近函数具有传递性，即 \(f(n)=\Theta (g(n)),g(n)=\Theta h(n)\Rightarrow f(n)=\Theta(h(n))\)。其他记号同理。

渐近函数具有自反性，即 \(f(n)=\Theta f(n)\)，对于 \(O,\Omega\) 记号同理。

\(\Theta\) 函数具有对称性，即 \(f(n)=\Theta(g(n))\) 当且仅当 \(g(n)=\Theta (f(n))\)。

渐近函数具有转置对称性，即 \(f(n)=O(g(n))\) 当且仅当 \(g(n)=\Omega f(n)\)；\(f(n)=o(g(n))\) 当且仅当 \(g(n)=\omega (f(n))\)。

二、使用主方法求解递归式

对于类似 \[ T(n)=aT(n/b)+f(n) \] 的递归式，通常使用主定理求解其渐近界。

2.1 \(\quad\) 主定理

定理（主定理） \(\quad\) 令 \(a\ge 1\) 和 \(b\ge 1\) 是常数，\(f(n)\) 是一个函数，\(T(n)\) 是定义在非负整数上的递归式： \[ T(n)=aT(n/b)+f(n) \] 我们将其中的 \(n/b\) 解释为 \(\lceil n/b \rceil\) 或者 \(\lfloor n/b \rfloor\)，那么 \(T(n)\) 有如下渐近界：

若对某个常数 \(\epsilon >0\) 有 \(f(n)=O(n^{\log_b a-\epsilon})\)，则有 \(T(n)=\Theta(n^{\log_ba})\)。
若 \(f(n)=\Theta(n^{\log_b a})\)，则 \(T(n)=\Theta(n^{\log_b a}\lg n)\)。
若对某个常数 \(\epsilon>0\) 有 \(f(n)=\Omega(n^{\log_b a+\epsilon})\)，且对某个常数 \(c<1\) 和所有足够大的 \(n\) 有 \(af(n/b)\le cf(n)\)，则 \(T(n)=\Theta(f(n))\)。

上面就是主定理。注意这三种情况并未覆盖 \(f(n)\) 的所有可能性，下面将说明如何正确地使用主定理。

2.2 \(\quad\) 使用主方法

我们把使用主定理求解递归式的方法称为主方法。我们只需要确定一个递归式对于主定理的哪种情况成立，即可得到解。

例子 \(\quad\) 对于下面的递归式，求解其渐近界。 \[ T(n)=9T(n/3)+n \]

对于这个递归式，我们有 \(a=9,b=3,f(n)=n\)，因此 \(n^{\log b a}=b^{\log_3 9}=\Theta(n^2)\)。由于 \(f(n)=O(n^{\log_39-\epsilon})\)，其中 \(\epsilon=1\)，因此可以应用于情况1，得到 \(T(n)=\Theta(n^2)\)。

例子 \(\quad\) 对于下面的递归式，求解其渐近界。 \[ T(n)=T(2n/3)+1 \]

其中，\(a=1,b=\frac{2}{3},f(n)=1\)，因此 \(n^{\log_b a}=n^0=1\)。由于 \(f(n)=\Theta(n^{\log _b a})=\Theta(1)\)，应用于情况2，得到 \(T(n)=\Theta(\lg n)\)。

例子 \(\quad\) 对于下面的递归式，求解其渐近界。 \[ T(n)=3T(n/4)+n\lg n \]

其中，\(a=3,b=4,f(n)=n\lg n\)，因此 \(n^{\log_b a}=O(n^{0.793})\)。由于 \(f(n)=\Omega(b^{\log_4 3-\epsilon})\)，其中 \(\epsilon\approx 0.2\)，因此，如果可以证明正则条件成立，可应用于情况3。当 \(n\) 足够大时，有 \(af(n/b)\le cf(n)\)，得到 \(T(n)=\Theta(n\lg n)\)。

上面给出了三种例子，只要算出 \(n^{\log_b a}\) 的渐近界，与 \(f(n)\) 比较，就可以求出递归式的渐近界。