本文共 726 字，大约阅读时间需要 2 分钟。

渐进关系

Big O的数学定义

n**2+O(n)=O(n2)

Big Omiga符号

Big Theta符号

Θ渐进上下界

O渐进上界（最坏情况） Ω渐进下界（最好情况）

Solving Recurrences

Substitution method代换法 1. guess the form of the solution 2. verify the induction(归纳法) 3. Solve the constants

Recursion-tree Method递归树法

Ex:T(n)=T(n/2)+T(n/4)+n**2

Master Method主方法

基于一个定理,但是很遗憾有限制，适用于某些情况 applies to recurrences, of the form T(n)=aT(n/b)+f(n) where a>=1,b>1 f(n) is asymptotically positive (f(n)>0 for n>=n0)

Compare f(n) vs. n**logb(a)

Case 1: smaller f(n)=O(n**logb(a)-epsilon) for some epsilon>0 =>T(n)=Theta(n**logb(a))

Case 2: f(n)=Theta(n**logb(a) *lgn**k)

for some k>=0

=>T(n)=Theta(n**logb(a)lgn**(k+1))

Case 3:f(n)=Omiga(n**logb(a)+epsilon)

for some epsilon>0 & af(n/b)<=(1-epsilon’)fn for some 0

转载地址：http://nojtb.baihongyu.com/