首页 > 其他 > 详细

主定理的证明

时间:2019-07-03 14:19:45      阅读:131      评论:0      收藏:0      [点我收藏+]

算法分析的那个定理.

Master Theorem
\[ T(n) = \begin{cases} \Theta(1), & \text{if } n = 1,\\ aT(n/b) + f(n), & \text{if } n>1. \end{cases} \]
where \(a\ge1\), \(b>1\) are constants and \(f\) is nonnegative. Then

  1. If \(f(n) = O(n^{\log_b a-\varepsilon})\) for some constant \(\varepsilon >0\), then \(T(n) = \Theta(n^{\log_b a})\).
  2. If \(f(n) = \Theta(n^{\log_b a})\), then \(T(n) = \Theta(n^{\log_b a}\lg n)\), where \(\lg n\) stands for \(\log_2 n\).
  3. If \(f(n) = \Omega(n^{\log_b a+\varepsilon})\) for some constant \(\varepsilon >0\), and if \(af(n/b)\le cf(n)\) for some constant \(c<1\) and all sufficiently large \(n\), then \(T(n) = \Theta(f(n))\).

直观上看就是比较 \(f(n)\)\(n^{\log_b a}\) 的阶数, 其中大的决定了 \(T(n)\) 的阶数; 如果阶数相同则乘 \(\lg n\).

证明: 先对 \(n\)\(b^k\), \(k\in\mathbb N\) 的情形证明, 下面的渐进符号都是对 \(n\)\(b^k\) 上的点而言的. 写出递归树, 高度为 \(\log_b n\), 故有 \(a^{\log_b n} = n^{\log_b a}\) 个叶, 从而
\[ T(n) = \Theta(n^{\log_b a}) + g(n), \] 其中
\[ g(n) = \sum_{j=0}^{\log_b n-1}a^j f(n/b^j). \]

Case 1. \(f(n) = O(n^{\log_b a-\varepsilon})\), 易得 \(g(n) = O(n^{\log_b a})\).

Case 2. \(f(n) = \Theta(n^{\log_b a})\), 易得 \(g(n) = \Theta(n^{\log_b a} \log_b n) = \Theta(n^{\log_b a} \lg n)\).

Case 3. 首先 \(g(n) = \Omega(f(n))\). 又 \(af(n/b)\le cf(n)\) for some constant \(c<1\) and sufficiently large \(n\). 即 \(a^j f(n/b^j) \le c^j f(n)\). 得
\[ \begin{align*} g(n) &= \sum_{j=0}^{\log_b n-1}a^j f(n/b^j)\&\le \sum_{j=0}^{\log_b n-1}c^j f(n) + O(1)\&\le f(n)\sum_{j=0}^\infty c^j + O(1)\&=O(f(n)). \end{align*} \]
\(g(n)=\Theta(f(n))\).

对一般的 \(n\) 证明略.

主定理的证明

原文:https://www.cnblogs.com/shiina922/p/11125847.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!