浅谈 主定理master theorem

打卡+坚持：2019.11.1 今日语录：做一个坚定的人，与时间赛跑，拖着世界前行

T(n) = a*T(n/b)+f(n) 其中a>=1, b>1,并且a和b是常数，f(n)是一个大于0 的递增函数( asymptotically positive function),不知道asymptotically positive function翻译对了没有 有三种可能的情况： 第1和3种情况可以理解为： T(n) = O(max(f(n), n^logb(a)))

接下来举几个例子来说明吧，顺便自己也练习一下 1.T(n) = 3T(n/2) + n²

a = 3, b = 2, f(n)=n² n^log₃2 < n² 即满足条件3 所以T(n) = O(n²)

2.T(n) = 4T(n/2) + n² a = 4, b = 2, f(n) = n² n^log₂4 = f(n) 满足条件2 可知k = 0， 所以T(n) = O(n² logⁿ)

3.T(n) = T(n/2) + 2ⁿ a = 1, b = 2, f(n) = 2ⁿ n^log₂1 < 2ⁿ 满足条件3，所以T(n) = O(2ⁿ)

4.T(n) = 2ⁿ T(n/2) + nⁿ a = 2ⁿ , b = 2, f(n) = nⁿ 注意：此处不满足，因为a不是常数 所以T(n) = O(2ⁿ T(n/2) + nⁿ)

5.T(n) = 16T(n/4) + n a = 16, b = 4, f(n) = n n^log₄16 = n² >f(n) = n 满足条件1，所以T(n) = O(n²)

6.T(n) = 2T(n/2) + nlogn a = 2, b = 2, f(n) = nlogn n^log₂2 < nlogn 所以T(n) = O(nlogn) 便给个超赞链接： http://people.csail.mit.edu/thies/6.046-web/master.pdf~

如有错误和不足，欢迎指正！！！谢谢大家！！！