主定理的证明,见主定理(Master Theorem)推导和理解(1)_Happy_Traveller的博客-CSDN博客,看几个实际case。
Case 1:求解递推方程:
,T(n)的计算复杂度
依据主定理,a=1, b=3, f(n) = n,那么
Case 2 : 求解递推方程:
, T(n)的计算复杂度
依据主定理,a=1, b=2/3, f(n) = 1,那么
Case 3 : 求解递推方程:
, T(n)的计算复杂度
依据主定理,a=3, b=4, ,那么
Case 4 : 求解递推方程:
,T(n)的计算复杂度
依据主定理,a=2, b=2, f(n) = nlogn,那么
所以case 4不能使用主定理
同时,直观上看,递推方程中,将原问题拆成b个子问题,同时需要a个这样的子问题,同时需要f(n)的操作合并这些子问题,所以,如果b越大,a越小,同时f(n)步骤越少,总体的计算就越少,就是越是好的算法。