05 Mar 2022 2235字 8分
CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~

求证：master theorem 的 Case 3，即当 a>bda>b^da>bd 时有

T(n)=cnd∑t=0log⁡bn(abd)t=Θ(nd(abd)log⁡bn)=Θ(nlog⁡ba)T(n)=cn^d\sum_{t=0}^{\log_bn}\left(\frac{a}{b^d}\right)^t\\ =\Theta\left(n^d\left(\frac{a}{b^d}\right)^{\log_bn}\right)\\ =\Theta\left(n^{\log_ba}\right)T(n)=cndt=0∑logb​n​(bda​)t=Θ(nd(bda​)logb​n)=Θ(nlogb​a)

证明：第一个等号已经在前两个 Case 中证明，下面分别证明后两个等式。

带入 x1=cnd,q=abd,m=1+log⁡bnx_1=cn^d ,q=\frac{a}{b^d}, m=1+\log_bnx1​=cnd,q=bda​,m=1+logb​n 到等比数列求和公式 S(m)=x1qm−1q−1S\left(m\right)=x_1\frac{q^m-1}{q-1}S(m)=x1​q−1qm−1​，有

T(n)=S(m)=x1qm−1q−1=x1(qmq−1−1q−1)=x1(qq−1qm−1−1q−1)T\left(n\right)=S\left(m\right)\\ =x_1\frac{q^m-1}{q-1}\\ =x_1\left(\frac{q^m}{q-1}-\frac{1}{q-1}\right)\\ =x_1\left(\frac{q}{q-1}q^{m-1}-\frac{1}{q-1}\right)T(n)=S(m)=x1​q−1qm−1​=x1​(q−1qm​−q−11​)=x1​(q−1q​qm−1−q−11​)

由于 qq−1,1q−1\frac{q}{q-1}, \frac{1}{q-1}q−1q​,q−11​ 均为常数，记常数 c’=qq−1=1+1q−1c’=\frac{q}{q-1}=1+\frac{1}{q-1}c’=q−1q​=1+q−11​，则有

T(n)=x1(qq−1qm−1−1q−1)=x1(c′qm−1−c′+1)=x1[c′(qm−1−1)+1]=Θ(x1[c′(qm−1−1)+1])T\left(n\right)=x_1\left(\frac{q}{q-1}q^{m-1}-\frac{1}{q-1}\right)\\ =x_1\left(c'q^{m-1}-c'+1\right)\\ =x_1\left[c'\left(q^{m-1}-1\right)+1\right]\\ =\Theta(x_1\left[c'\left(q^{m-1}-1\right)+1\right])T(n)=x1​(q−1q​qm−1−q−11​)=x1​(c′qm−1−c′+1)=x1​[c′(qm−1−1)+1]=Θ(x1​[c′(qm−1−1)+1])

由于 a>bda>b^da>bd ，因此 q=abd>1,lim⁡m→∞qm−1=∞≫1q=\frac{a}{b^d}>1, \lim_{m\to\infty}q^{m-1}=\infty\gg 1q=bda​>1,limm→∞​qm−1=∞≫1。同时 c,c’c,c’c,c’ 均为常数，则有

T(n)=Θ(x1[c′(qm−1−1)+1])=Θ(x1qm−1)=Θ(cnd(abd)log⁡bn)=Θ(nd(abd)log⁡bn)T\left(n\right)=\Theta(x_1\left[c'\left(q^{m-1}-1\right)+1\right])\\ =\Theta(x_1q^{m-1})\\ =\Theta\left(cn^d\left(\frac{a}{b^d}\right)^{\log_bn}\right)\\ =\Theta\left(n^d\left(\frac{a}{b^d}\right)^{\log_bn}\right)T(n)=Θ(x1​[c′(qm−1−1)+1])=Θ(x1​qm−1)=Θ(cnd(bda​)logb​n)=Θ(nd(bda​)logb​n)

于是我们证明了第二个等号，接下来证明第三个等号。

T(n)=Θ(nd(abd)log⁡bn)=Θ(ndalog⁡bn(b−d)log⁡bn)=Θ(ndalog⁡bn(blog⁡bn)−d)=Θ(ndalog⁡bnn−d)=Θ(alog⁡bn)=Θ((nlog⁡na)log⁡bn)=Θ(nlog⁡ba)T\left(n\right)=\Theta\left(n^d\left(\frac{a}{b^d}\right)^{\log_bn}\right)\\ =\Theta\left(n^da^{\log_bn}\left({b^{-d}}\right)^{\log_bn}\right)\\ =\Theta\left(n^da^{\log_bn}\left({b^{\log_bn}}\right)^{-d}\right)\\ =\Theta\left(n^da^{\log_bn}n^{-d}\right)\\ =\Theta\left(a^{\log_bn}\right)\\ =\Theta\left(\left(n^{\log_na}\right)^{\log_bn}\right)\\ =\Theta\left(n^{\log_ba}\right)T(n)=Θ(nd(bda​)logb​n)=Θ(ndalogb​n(b−d)logb​n)=Θ(ndalogb​n(blogb​n)−d)=Θ(ndalogb​nn−d)=Θ(alogb​n)=Θ((nlogn​a)logb​n)=Θ(nlogb​a)

假设 T(n)=2⋅T(n2)+32⋅nT(n)=2\cdot T(\frac{n}{2})+32\cdot nT(n)=2⋅T(2n​)+32⋅n，下面的过程错在哪？

• Inductive Hypothesis: T(n)=O(nlog⁡n)T\left(n\right)=O\left(n\log n\right)T(n)=O(nlogn)
• Base case: T(2)=2=O(1)=O(2log⁡2)T\left(2\right)=2=O\left(1\right)=O\left(2\log 2\right)T(2)=2=O(1)=O(2log2)
• Inductive Step:
  1. Suppose that ∀n<k,T(n)=O(nlog⁡n)\forall n<k,T\left(n\right)=O\left(n\log n\right) ∀n<k,T(n)=O(nlogn).
  2. Then T(k)=2⋅T(k2)+32⋅kT\left(k\right)=2\cdot T\left(\frac{k}{2}\right)+32\cdot kT(k)=2⋅T(2k​)+32⋅k by definition.
  3. So T(k)=2⋅O(k2logk2)+32⋅kT\left(k\right)=2\cdot O\left(\frac{k}{2}log\frac{k}{2}\right)+32\cdot kT(k)=2⋅O(2k​log2k​)+32⋅k by induction.
  4. But that’s T(k)=O(klog⁡k)T\left(k\right)=O\left(k\log k\right)T(k)=O(klogk), so the I.H. holds for n=kn=kn=k.
• Conclusion: By induction, ∀n,T(n)=O(nlog⁡n)\forall n,T\left(n\right)=O\left(n\log n\right)∀n,T(n)=O(nlogn).

Inductive Step 的第 4 步错了，该步骤中不能使用 T(k)=O(klog⁡k)T\left(k\right)=O\left(k\log k\right)T(k)=O(klogk) 这一论据，因为第一步中的假设成立条件是 ∀n<k\forall n<k∀n<k。换言之，该步骤将需要证明的内容直接作为论据了。

实际上由 master theorem ，b=2,d=1,a=2=bdb=2,d=1,a=2=b^db=2,d=1,a=2=bd，应有 T(n)=O(ndlog⁡n)=O(n2log⁡n)T\left(n\right)=O\left(n^d\log n\right)=O\left(n^2\log n\right)T(n)=O(ndlogn)=O(n2logn)。