个人学习——算法：递归式复杂度计算(主方法)

在分析根据递归方程分析算法的时间复杂度时&＃xff0c;常见到如下形式的方程&＃xff0c;
T(n) &＃61; a * T(n/b) &＃43; f(n)
a >&＃61; 1&＃xff0c;b > 1&＃xff0c;f(n)一般是个简单函数

这时可以有2种方法&＃xff0c;来计算时间复杂度&＃xff1a;
一是用递归树&＃xff0c;逐层代入原式&＃xff0c;最终形成一个级数&＃xff0c;然后用一个函数来表达&＃xff0c;得到T(n)。
二是应用主项定理Master Method 。其实&＃xff0c;主项定理也就是对递归树方法的一种归纳&＃xff0c;形成了固定的计算方式&＃xff0c;并分三种情形来计算&＃xff1a;

logb a 是以b为底
nlogb a &＃xff1a;logb a为n的幂数

1.若对于某常数ε>0&＃xff0c;有f(n) &＃61; O(nlogb a-ε )&＃xff0c;则T(n) &＃61; O(nlogb a ) &＃xff08;取较大者&＃xff0c;较大者变化得快&＃xff09;
2.若f(n) &＃61; O(nlogb a )&＃xff0c;则T(n) &＃61; O(nlogb a *logn)
3.若f(n) &＃61; O(nlogb a&＃43;ε )&＃xff0c;且对于某常数c>1和所有充分大的正整数n&＃xff0c;有af(n/b)≤cf(n)&＃xff0c;则T(n)&＃61;O(f(n))&＃xff08;取较大者&＃xff09;

注意&＃xff1a;大小比较是在多项式的意义上的大于和小于
T(n) &＃61; 2T(n/2) &＃43; nlgn 这样的是不能用主方法的&＃xff0c;不是多项式的意义上的比较&＃xff0c;对于任何正整数都满足。
T(n) &＃61; 2T(n/2) &＃43; nlogn &＃61; O(nlogn*logn)&＃xff08;由递归法得&＃xff09;