给定

T ( n ) = { <mstyle displaystyle="false" scriptlevel="0"> 1 , </mstyle> <mstyle displaystyle="false" scriptlevel="0"> n = 1 </mstyle> <mstyle displaystyle="false" scriptlevel="0"> a T ( <mstyle displaystyle="true" scriptlevel="0"> n b </mstyle> ) + f ( n ) , </mstyle> <mstyle displaystyle="false" scriptlevel="0"> <mtext> otherwise </mtext> </mstyle> T(n)=\begin{cases}1,&n=1\\a T(\dfrac{n}{b})+f(n),&\text{otherwise}\end{cases} T(n)={1,aT(bn​)+f(n),​n=1otherwise​

试计算 T ( n ) T(n) T(n)。

令 c c r i t = log ⁡ b a c_{crit}=\log_ba ccrit​=logb​a：

  • 若 f ( n ) = O ( n c ) f(n)=O(n^c) f(n)=O(nc)且 c < c c r i t c<c_{crit} c<ccrit​则有 T ( n ) = Θ ( n c c r i t ) T(n)=\Theta(n^{c_{crit}}) T(n)=Θ(nccrit​)
  • 若 ∃ k \exists k ∃k使得 f ( n ) = n c c r i t log ⁡ k n f(n)=n^{c_{crit}}\log^kn f(n)=nccrit​logkn，则有： T ( n ) = { <mstyle displaystyle="false" scriptlevel="0"> Θ ( n c c r i t log ⁡ k + 1 n ) , </mstyle> <mstyle displaystyle="false" scriptlevel="0"> k > − 1 </mstyle> <mstyle displaystyle="false" scriptlevel="0"> Θ ( n c c r i t log ⁡ log ⁡ n ) , </mstyle> <mstyle displaystyle="false" scriptlevel="0"> k = − 1 </mstyle> <mstyle displaystyle="false" scriptlevel="0"> Θ ( n c c r i t ) , </mstyle> <mstyle displaystyle="false" scriptlevel="0"> k < − 1 </mstyle> T(n)=\begin{cases}\Theta(n^{c_{crit}}\log^{k+1}n),&k>-1\\\Theta(n^{c_{crit}}\log\log n),&k=-1\\\Theta(n^{c_{crit}}),&k<-1\end{cases} T(n)=⎩⎪⎨⎪⎧​Θ(nccrit​logk+1n),Θ(nccrit​loglogn),Θ(nccrit​),​k>−1k=−1k<−1​
  • 若 f ( n ) = Ω ( n c ) f(n)=\Omega(n^c) f(n)=Ω(nc)且 c > c c r i t c>c_{crit} c>ccrit​则有 T ( n ) = Θ ( f ( n ) ) T(n)=\Theta(f(n)) T(n)=Θ(f(n))