函数增长

重点

系统的阐述算法时间复杂度的数学定义即渐进时间。

• 渐进记号 \(O\)、\(\Omega\)、\(\Theta\) 的定义及其使用
• 标准复杂性函数及其大小关系
• 和式界的证明方法

渐进记号

前面我们分析算法的时间复杂度时，会用类似“线性”，“二次”等字眼来描述，现在介绍一种更标准的表示方法即渐进记号。

渐紧记号

渐紧记号表示一个算法随着输入规模增大，其运行时间被夹在两个同阶的函数之间，体现一种紧的界限，严格的数学定义如下：

渐近紧确界

对一个给定的函数 \(g(n)\)，用 \(\Theta(g(n))\) 表示下面的函数集合：

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

称 \(g(n)\) 是 \(f(n)\) 的一个渐进紧确界。

下面我们尝试用这个定义证明 \(\dfrac{1}{2}n^2 - 3n = \Theta(n^2)\) 成立：

证明

目标是找到合适的正常数 \(c_1, c_2, n_0\)，使得当 \(n \geqslant n_0\) 时，有：

\[ c_1n^2 \leqslant \frac{1}{2}n^2 - 3n \leqslant c_2n^2 \]

不等式整体除以 \(n^2\)，得到：

\[ c_1 \leqslant \frac{1}{2} - \frac{3}{n} \leqslant c_2 \]

取 \(c_2 = \dfrac{1}{2}\)，则只要 \(n \geqslant 1\)，右边不等式成立；取 \(c_1 = \dfrac{1}{14}\) 则对任何的 \(n \geqslant 7\)，左边不等式成立，因此得到满足条件的正常数：\(c_1 = \dfrac{1}{14}\), \(c_2 = \dfrac{1}{2}\), \(n_0 = \max{(1, 7)} = 7\)。

渐进上界记号

\(\Theta\) 记号同时给出了函数的上界和下界，当函数只有一个渐进上界时，使用 \(O\) 记号，严格数学定义如下：

渐进上界

对一个给定的函数 \(g(n)\)，用 \(O(g(n))\) 表示下面的函数集合：

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

称 \(g(n)\) 是 \(f(n)\) 的一个渐进上界。

回顾插入排序，其最坏情况就有一个 \(O(n^2)\) 的渐进上界。

渐进下界记号

正如 \(O\) 记号给出了函数的渐进上界，\(\Omega\) 记号以为函数存在一个渐进下界，严格数学定义如下：

渐近紧确界

对一个给定的函数 \(g(n)\)，用 \(\Theta(g(n))\) 表示下面的函数集合：

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

称 \(g(n)\) 是 \(f(n)\) 的一个渐进下界。

根据上面的这些记号的定义，我们可以得出一个非常显然的定理：

记号之间的关系

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

上述定理很好地总结了三个渐进记号之间的关系。

比较各种函数

实属的许多关系性质也适用于渐进比较。下面假定 \(f(n)\) 和 \(g(n)\) 渐进为正。

传递性