CLRS笔记3：函数的增长

渐近记号
θ(g(n))={f(n):存在正常数c1,c2和n0，使对所有的n>=n0，有0 <= c1g(n) <= f(n) <= c2g(n)}
Ο(g(n))={f(n):存在正常数c和n0，使对所有的n>=n0，有0 <= f(n) <= cg(n)}
Ω(g(n))={f(n):存在正常数c和n0，使对所有的n>=n0，有0 <= cg(n) <= f(n)}
o(g(n))={f(n):对任意正常数c，存在常数n0>0，使对所有的n>=n0，有0 <= f(n) < cg(n)}
ω(g(n))={f(n):对任意正常数c，存在常数n0>0，使对所有的n>=n0，有0 <= cg(n) < f(n)}

传递性
f(n) = θ(g(n)) 和 g(n) = θ(h(n)) 蕴含f(n) = θ(h(n))
f(n) = Ο(g(n)) 和 g(n) = Ο(h(n)) 蕴含f(n) = Ο(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) = Ο(f(n)) f(n) = Ω(f(n))

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

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

类比
f(n) = Ο(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

标准记号和常用函数
函数f(n)单调递增：若m <= n蕴含f(m) <= f(n)
函数f(n)单调递减：若m <= n蕴含f(m) >= f(n)
函数f(n)严格递增：若m <  n蕴含f(m) <  f(n)
函数f(n)严格递减：若m <  n蕴含f(m) >  f(n)

下取整和上取整：x-1 < [_ x _] <= [- x -] < x+1

取模： a mod n = a - [_a/n_]n

多项式：给定一个正整数d，n的d次多项式是具有如下形式的函数p(n)：
        d
p(n) = ∑ ain^i
       i=0

指数式：对任意实数a>0、m和n，有下列恒等式：
a^0 = 1, a^1 = a, a^-1 = 1/a
(a^m)^n = a^mn, (a^m)^n = (a^n)^m, a^ma^n = a^m+n

对数：
lgn = log2n
lnn = logen
lg^kn = (lgn)^k
lglgn = lg(lgn)

阶乘：
记号n!定义为对所有整数n >= 0，
n! { 1         如果n=0
     n*(n-1)!  如果n > 0

函数迭代：
f(i)(n) = { n            如果i=0
            f(f(i-1)(n)) 如果i>0

多重对数函数：
lg*n = min{i >= 0: lg(i)n <=1}

斐波那契数：
斐波那契数递归地定义为：
F0 = 0, F1 = 1, Fi = Fi-1 + Fi-2 当i >= 2