author: cust--ZK
分治算法中有一些算法,仅仅用分支递推公式无法计算出其时间复杂性,因为它的递推方程带有一个幂项,虽然依靠迭代我们仍然可以求出其递推公式,但是这么做未免太复杂浪费时间。
这时候我们有一个通法,那就是主定理(master theorem),根据情况直接套公式就能求出时间复杂性。主定理形式如下
设f是满足递推关系
的增函数,其中$n=b^k$,k是一个正整数,$a \geq1$,b是大于1的整数,c和d是实数,满足c是正的且b是非负的,那么
假设N是b的幂,令$N = b^m$,假设f(1) = 1,则有
将以上累加得
因此
如果$a>b^k$
如果$a=b^k$
如果$a < b^k$
原文:https://www.cnblogs.com/zhaoke271828/p/12764889.html