分治法主定理

主定理的证明

假设有递归式：
$T(n) = aT(\frac{n}{b}) + f(n)$T(n)=aT(bn​)+f(n)
证明：
$T(n) = aT(n/b) + f(n)$T(n)=aT(n/b)+f(n)$= a\big[aT(n/b^2)+f(n/b)\big] + f(n)$=a[aT(n/b2)+f(n/b)]+f(n)$= a^2T(n/b^2) + f(n) + af(n/b) ~\,$=a2T(n/b2)+f(n)+af(n/b) $= a^{k}T(n/b^k) + \sum_{j=0}^{k-1} a^j f(n/b^j) ~~~~$=akT(n/bk)+j=0∑k−1​ajf(n/bj)    $= \cdots ~(不妨设n是b的幂)~~~~~~~~~~~~$=⋯ (不妨设n是b的幂)            $= a^{log_b^n}T(1) + \sum_{j=0}^{log_b^n-1} a^j f(n/b^j) ~~$=alogbn​T(1)+j=0∑logbn​−1​ajf(n/bj)  
由对数的换底公式：$a^{log_b^n} =b^{log_b^{(a^{log_b^n})}} =b^{log_b^a log_b^n} =b^{log_b^n log_b^a}= b^{log_b^{(n^{log_b^a})}}=n^{log_b^a}$alogbn​=blogb(alogbn​)​=blogba​logbn​=blogbn​logba​=blogb(nlogba​)​=nlogba​

所以原递归式的渐进复杂度为$O(n^{log_b^a}) + \sum_{j=0}^{log_b^n-1} a^j f(n/b^j)$O(nlogba​)+j=0∑logbn​−1​ajf(n/bj)

简单起见，下面只考虑 $f(n) = n^k$f(n)=nk 的情形：
$\sum_{j=0}^{log_b^n-1} a^j f(n/b^j)$j=0∑logbn​−1​ajf(n/bj)$= \sum_{j=0}^{log_b^n-1} a^j (n/b^j)^k ~~~~~~~$=j=0∑logbn​−1​aj(n/bj)k       $= n^k\sum_{j=0}^{log_b^n-1} (a/b^k)^j ~~~~~~~$=nkj=0∑logbn​−1​(a/bk)j       $= \left\{ \begin{array}{lr} n^k \left(\frac{1-(a/b^k)^{log_b^n}}{1-a/b^k}\right), & \text{如果$a\neq b^k$}\\ &\\ n^k(log_b^n-1), & \text{如果$a = b^k$} \end{array} \right.$=⎩⎪⎨⎪⎧​nk(1−a/bk1−(a/bk)logbn​​),nk(logbn​−1),​如果a​=bk如果a=bk​$= \left\{ \begin{array}{lr} O(n^k) , & \text{如果$a < b^k(k>log_b^a)$}\\ &\\ O(n^{log_b^a}), & \text{如果$a> b^k$}\\ &\\ O(n^klog_b^n)=O(n^{log_b^a}log_b^n), & \text{如果$a = b^k$} \end{array} \right.$=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​O(nk),O(nlogba​),O(nklogbn​)=O(nlogba​logbn​),​如果a<bk(k>logba​)如果a>bk如果a=bk​

综上所述，对 $T(n) = aT(\frac{n}{b}) + f(n)$T(n)=aT(bn​)+f(n) 的情形：
$T(n)= \left\{ \begin{array}{lr} O(n^k) , & \text{如果$a< b^k(k>log_b^a)$}\\ &\\ O(n^{log_b^a}), & \text{如果$a> b^k$}\\ &\\ O(n^klog_b^n)=O(n^{log_b^a}log_b^n), & \text{如果$a = b^k$} \end{array} \right.$T(n)=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​O(nk),O(nlogba​),O(nklogbn​)=O(nlogba​logbn​),​如果a<bk(k>logba​)如果a>bk如果a=bk​

减治法主定理