主定理的数学证明
author: cust--ZK
分治算法中有一些算法,仅仅用分支递推公式无法计算出其时间复杂性,因为它的递推方程带有一个幂项,虽然依靠迭代我们仍然可以求出其递推公式,但是这么做未免太复杂浪费时间。
SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。这时候我们有一个通法,那就是主定理(master theorem),根据情况直接套公式就能求出时间复杂性。主定理形式如下
设f是满足递推关系
$f(n) = af(n/b) + cn^d$
的增函数,其中$n=b^k$,k是一个正整数,$a \geq1$,b是大于1的整数,c和d是实数,满足c是正的且b是非负的,那么
假设N是b的幂,令$N = b^m$,假设f(1) = 1,则有
$f(b^m) = af(b^{m-1})+(b^k)^{m}$ $\frac{f(b^m)}{a^m} = \frac{f(b^{m-1})}{a^{m-1}}+(\frac{b^k}{a})^{m}$ ...将以上累加得
$\frac{f(b^m)}{a^m} = \sum\limits_{i=0}^{m}(\frac{b^k}{a})^i$因此
$f(b^m) = a^m \sum\limits_{i=0}^{m}(\frac{b^k}{a})^i$如果$a>b^k$
$f(N)=O(a^m)=O(N^{log_ba})$如果$a=b^k$
$f(N)=O(a^mlog_bN)=O(N^klogN)$如果$a < b^k$
$f(N)=\frac{(b^k/a)^{m+1} - 1}{b^k/a - 1} = O(a^m(\frac{b^k}{a})^{m})=O(N^k)$ ----author ZK更多精彩