先了解一些有关符号

渐进符号 

渐进符号 非渐进符号 含义
f(n)=O(g(n))f(n)=O(g(n)) f(n)≤cg(n)f(n)≤cg(n) g是f的上界
f(n)=o(g(n))f(n)=o(g(n)) f(n)<cg(n)f(n)<cg(n) g是f的严格上界
f(n)=Ω(g(n))f(n)=Ω(g(n)) f(n)≥cg(n)f(n)≥cg(n) g是f的下界
f(n)=ω(g(n))f(n)=ω(g(n)) f(n)>cg(n)f(n)>cg(n) g是f的严格下界
f(n)=Θ(g(n))f(n)=Θ(g(n)) c1g(n)≤f(n)≤c2g(n)c1g(n)≤f(n)≤c2g(n) g是f的确界

一个典型的递归式

 

T(n)=aT(n/b)+f(n)

分析：总的来说，规模为n的问题，可分为a个规模为n/b的子问题，每个子问题可通过f(n)的事件解决。

主定理

主定理通过递归树导出，主要思想是：

比较nlogbanlogb⁡a与f(n)f(n)的渐进大小关系，渐进关系大的决定复杂度T(n)。

第一种情况：nlogba=ω(f(n))nlogb⁡a=ω(f(n)) ，T(n)=Θ(nlogba)T(n)=Θ(nlogb⁡a)

例：T(n)=9T(n/3)+nT(n)=9T(n/3)+n

nlogba=nlog39=n2=ω(n)nlogb⁡a=nlog3⁡9=n2=ω(n)

知 T(n)=Θ(n2)T(n)=Θ(n2)

第二种情况：nlogba=o(f(n))nlogb⁡a=o(f(n))，T(n)=Θ(f(n))T(n)=Θ(f(n))

应用该公式，还要必须满足：

存在实数c，且c<1c<1时，有af(n/b)≤cf(n)af(n/b)≤cf(n)。

例：T(n)=3T(n/4)+nlog2nT(n)=3T(n/4)+nlog2⁡n

nlogba=nlog43≈n0.792=o(nlog2n)nlogb⁡a=nlog4⁡3≈n0.792=o(nlog2⁡n)

且由34nlog2n4≤cnlog2n34nlog2⁡n4≤cnlog2⁡n，可得34<c<134<c<1

知 T(n)=Θ(nlog2n)T(n)=Θ(nlog2⁡n)

第三种情况：nlogba=Θ(f(n))nlogb⁡a=Θ(f(n))，T(n)=Θ(nlogbalog2n)T(n)=Θ(nlogb⁡alog2⁡n)

例：T(n)=T(3n/4)+1T(n)=T(3n/4)+1

nlogba=nlog431=n0=Θ(1)nlogb⁡a=nlog43⁡1=n0=Θ(1)

知 T(n)=Θ(log2n)T(n)=Θ(log2⁡n)

注意

主定理为未包含所有递归式情况，有以下情况不被包含：