算法导论（一）：渐进记号
算法中，常用极限情况度量一个函数的好坏，因此引入了渐进函数的概念。在渐进函数中，有以下五种渐进记号：Ο、Θ、Ω、ο、ω。
假设有函数f(n)与函数g(n)，如果令函数f(n)为实数a，函数g(n)为实数b，则有以下类比：
f(n)=Ο(g(n)) 类似于 a≤b
f(n)=Ω(g(n)) 类似于 a≥b
f(n)=Θ(g(n)) 类似于 a=b
f(n)=ο(g(n)) 类似于 a<b
f(n)=ω(g(n)) 类似于 a>b
Ο记号
Ο记号表示渐进上界，即存在正常数c与n0，使得当n≥n0时，有0≤f(n)≤cg(n)。则认为f(n)=Ο(g(n))。（读作：大Ο(g(n))）
Θ记号
Θ记号表示渐进准确界，即存在正常数c1，c2与n0，使得当n≥n0时，有0≤c1g(n)≤f(n)≤c2g(n)。则认为f(n)=Θ(g(n))。（读作：Θ(g(n))）
Ω记号
Ω记号表示渐进下界，即存在正常数c与n0，使得当n≥n0时，有0≤cg(n)≤f(n)。则认为f(n)=Ω(g(n))。（读作：大Ω(g(n))）
ο记号
ο记号表示非渐进上界，即存在正常数n0，对任意的常数c>0，使得当n≥n0时，有0≤f(n)<cg(n)。则认为f(n)=ο(g(n))。（读作：小ο(g(n))）
直观上可以理解，当n趋近无穷时，有limn→∞(f(n)/g(n))=0
ω记号
ω记号表示非渐进下界，即存在正常数n0，对任意的常数c>0，使得当n≥n0时，有0≤cg(n)<f(n)。则认为f(n)=ω(g(n))。（读作：小ω(g(n))）
直观上可以理解，当n趋近无穷时，有limn→∞(f(n)/g(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)=ο(g(n))且g(n)=ο(h(n))→f(n)=ο(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)=ο(g(n)) 当且仅当 g(n)=ω(f(n))