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+1
取模： a mod n = a - 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
页:
[1]