渐近记号

渐近紧界
既有渐近上界，又有渐近下界
Θ(g(n))={ f(n):存在正常数c1，c2和n0，使对所有的n>=n0，有0<=c1g(n)<=f(n)<=c2g(n) }
渐近上界
O(g(n))={ f(n): 存在正常数c和n0，使对所有n>=n0，有0<=f(n)<=cg(n) }
非渐近紧确上界
o(g(n))={ f(n): 对任意正常数c，存在常数n0>0，使对所有的n>=n0，有0<=f(n)<cg(n) }
渐近下界
Ω(g(n))={ f(n):存在正常数c和n0，使对所有n>=n0，有0<=cg(n)<=f(n) }
非渐近紧确下界
ω(g(n))={ f(n) 对任意正常数c，存在常数n0>0，使对所有的n>=n0，有0<=cg(n)<f(n) }

定理3.1
对于任意两个函数f(n)和g(n)，我们有f(n) = Θ(g(n))，当且仅当 f(n) = O(g(n)) 且 f(n) = Ω(g(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))

还有一些符号，打字不方便。这章主要是帮助回顾一下各种函数的性质，方便今后分析算法。