通用形式：T(n) = aT(n/b) + f(n)
所以我必须将 n^logb(a) 与 f(n) 进行比较
if n^logba > f(n) is case 1 and T(n)=Θ(n^logb(a))
if n^logba < f(n) is case 2 and T(n)=Θ((n^logb(a))(logb(a)))
那是对的吗？或者我误解了什么？
那么案例3呢？什么时候适用？
求解递归的主定理
重复出现在解决复杂问题的分而治之策略中。
它解决什么问题？
- 它解决了形式的重复
T(n) = aT(n/b) + f(n).
-
a应大于或等于1。这意味着该问题至少被缩减为更小的子问题一次。至少需要一次递归。
-
b应大于 1。这意味着在每次递归时，问题的规模都会减小到更小的规模。如果b不大于1，这意味着我们的子问题的规模不小。
-
f(n)对于相对较大的值必须为正n.
考虑下图：
假设我们有尺寸问题n待解决。在每一步中，问题可以分为a子问题，并且每个子问题的规模较小，其中规模减小了一个因子b.
上面的说法简单来说就是尺寸问题n可以分为a规模相对较小的子问题n/b.
另外，上图表明，最终当我们将问题多次划分时，每个子问题都会很小，以至于可以在常数时间内解决。
对于下面的推导请考虑log到基地b.
让我们这么说H是树的高度，那么H = logn。叶子的数量=a^logn.
- 1 级完成的总工作量：
f(n)
- 2 级完成的总工作量：
a * f(n/b)
- 1 级完成的总工作量：
a * a * f(n/b2)
- 最后一级完成的总工作量：
number of leaves * θ(1)。这等于n^loga
主定理的三种情况
Case 1:
现在让我们假设每个级别的操作成本都以一个重要因素增加，并且当我们到达叶级别时，f(n)变得比该值更小的多项式n^loga。那么整体运行时间将很大程度上取决于最后一级的成本。因此T(n) = θ(n^loga).
Case 2:
让我们假设每个级别上的操作成本大致相等。在这种情况下f(n)大致等于n^loga。因此，总运行时间为f(n)乘以总层数。
T(n) = θ(n^loga * logn) where k can be >=0. Where logn是一棵树的高度k >= 0.
注：这里k+1是logn中log的基数
Case 3:
让我们假设每个级别上的操作成本都在每个级别上减少一个重要因素，并且当我们到达叶级别时，值f(n)变得比该值更大的多项式n^loga。那么总的运行时间将主要由第一级的成本决定。因此T(n) = θ(f(n)).
如果您有兴趣更详细的阅读和练习示例，请访问我的博客条目掌握解决递归问题的方法 http://techieme.in/solving-recurrences-master-method/
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
