算法导论（三）－－函数的增长

前面看到用于表示运行时间的Ө记号，现在给出它的定义：
Ө(g(n)) = { f(n)：存在正常数c1，c2和n0，使对所有的n≥n0，有0≤c1*g(n)≤f(n)≤c2*g(n) }。
从 定义上看，Ө(g(n))是一个集合，g(n)是一个函数，而f(n)为Ө(g(n))集合里的一个元素，可以写成“ f(n)∈Ө(g(n))”，但通常我们直接写成“f(n)＝Ө(g(n))”。比如我们某个算法的运行时间为f(n) = 2n^2+3n+5，我们要证明f(n)属于Ө(n^2)，即g(n)=n^2：当n大于某值时，应该满足条件 c1*n^2 ≤ 2n^2 + 3n + 5 ≤ c2*n^2。我们选择c1=1，c2=3，当n≥5时，不等式成立。所以我们可以说f(n) = 2n^2+3n+5 = Ө(n^2)。

对于任何一个多项式p(n) = ∑ai*n^i (i=0→d)，当ad大于0（即最高次项的系数大于0）时，p(n) = Ө(n^d)。换而言之，二次项系数为正的二次多项式属于Ө(n^2)，三次项系数为正的三次多项式属于Ө(n^3)。

Ө记号渐近给出了一个函数的上界和下界。当只有渐近上界时，使用O记号。它的定义为：
O(g(n)) = { f(n)：存在正常数c和n0，使对所有的n≥n0，有0 ≤ f(n) ≤ c*g(n) }。

相应的，Ω记号给出了渐近下界：
Ω(g(n)) = { f(n)：存在正常数c和n0，使对所有的n≥n0，有0 ≤ c*g(n) ≤ f(n) }。

O记号在提供的渐近上界可能是也可能不是渐近紧确的。例如2n^2 = O(n^2)是渐近紧确的，而2n=O(n^2)就不是渐近紧确的。o记号（小写字母o）表示非渐近紧确的上界：
o(g(n)) = { f(n)：对任意正常数c，存在常数n0>0，使对所有的n≥n0，有0 ≤ f(n) ≤ c*g(n) }。
注意到这里是任意正常数c，而不是存在正常数c。这是它与O记号的区别。
当n趋于无穷时，函数f(n)相对于g(n)就不重要了，即 lim(f(n)/g(n)) = 0 (n→∞)。

ω记号与Ω记号的关系和o记号与O记号的关系一样，它表示非渐近紧确的下界：
o(g(n)) = { f(n)：对任意正常数c，存在常数n0>0，使对所有的n≥n0，有 0 ≤ c*g(n) < f(n) }。
当n趋于无穷时，函数f(n)相对于g(n)来说变得任意大了，即lim(f(n)/g(n)) = ∞ (n→∞)。

渐近记号的一些性质：

传递性：
f(n) = Ө(g(n)) 和 g(n) = Ө(h(n)) => f(n) = Ө(h(n))
f(n) = O(g(n)) 和 g(n) = O(h(n)) => f(n) = O(h(n))
f(n) = Ω(g(n)) 和 g(n) = Ω(h(n)) => f(n) = Ω(h(n))
f(n) = o(g(n)) 和 g(n) = o(h(n)) => f(n) = o(h(n))
f(n) = ω(g(n)) 和 g(n) = ω(h(n)) => f(n) = ω(h(n))

自反性：
f(n) = Ө(f(n))
f(n) = O(f(n))
f(n) = Ω(f(n))

对称性：
f(n) = Ө(g(n)) 当且仅当 g(n) = Ө(f(n))

转置对称性：
f(n) = O(g(n)) 当且仅当 g(n) = Ω(f(n))
f(n) = o(g(n)) 当且仅当 g(n) = ω(f(n))

因为这些性质，我们可以把两个函数f与g的渐近比较与实数a和b的比较类比起来：
f(n) = O(g(n)) ≈ a ≤ b
f(n) = Ω(g(n)) ≈ a ≥ b
f(n) = Ө(g(n)) ≈ a = b
f(n) = o(g(n)) ≈ a < b
f(n) = ω(g(n)) ≈ a > b