主要的方法论学习与实践案例研究

文章结构概览

• 递归算法时间复杂度分析-主定理应用实例
  • • (1)T(n)=2T(n/4)+1
    • (2)T(n)=2T(n/4)+\sqrt{n}
    • (3)T(n)=2T(n/4)+n
    • (4)T(n)=2T(n/4)+n^2
    • (6)T(n)=7T(n/2)+\Theta(n^2)
    • 解题核心要点

递归式求解时间复杂度-主方法例题

(1)T(n)=2T(n/4)+1

解：已知a=2, b=4, f(n)=1，并且n^{\log_b a}=n^{\log_4 2}=n^{\frac{1}{2}}。

由此可设定\epsilon = \frac{1}{2}，从而得出f(n)=1=n^{\frac{1}{2}-\epsilon}。

因此，f(n)=O(n^{\frac{1}{2}-\epsilon})。依据主定理中的第一种情形，

可以推得T(n)=\Theta(n^{\frac{1}{2}})。

(2)T(n)=2T(n/4)+\sqrt{n}

解：由于a=2, b=4, f(n)=\sqrt{n}，并且\log_b a=\log_4 2=n^{\frac{1}{2}}，

因此，$f(n