通用形式：T(n) = aT(n/b) + f(n)
所以我必须将 n^logb(a) 与 f(n) 进行比较
如果n^logba>f(n)是案例 1并且T(n)=Θ(n^logb(a))
如果n^logba<f(n)是情况 2并且T(n)=Θ((n^logb(a))(logb(a)))
那是对的吗？还是我误解了什么？
那么案例3呢？什么时候适用？
5052 次
2 回答
26
解决递归的主定理
重复发生在解决复杂问题的分而治之的策略中。
它解决了什么问题？
- 它解决了表单的重复问题
T(n) = aT(n/b) + f(n)。 a应该大于或等于1。这意味着问题至少被简化为一个较小的子问题一次。至少需要一次递归。b应该大于 1。这意味着在每次递归时，问题的大小都会减小到更小的大小。如果b不大于 1，这意味着我们的子问题不是较小的。f(n)对于相对较大的 值，必须为正n。
考虑下图：
假设我们有一个尺寸问题n要解决。在每一步，问题都可以分为a子问题，每个子问题的规模都较小，其中规模缩小了b.
上面的简单表述意味着一个大小的问题n可以分成a大小相对较小的子问题n/b。
另外，上图显示，最后当我们多次划分问题时，每个子问题会很小，可以在恒定时间内解决。
对于以下推导，请考虑logbase 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
大师定理的三种情况
情况1：
现在让我们假设每个级别的操作成本都增加了一个重要因素，并且当我们到达叶级别时， 的值f(n)变得多项式地小于值n^loga。那么整体运行时间将在很大程度上受到最后一级的成本的支配。因此T(n) = θ(n^loga)。
案例二：
让我们假设每个级别的操作成本大致相等。在那种情况下f(n)大致等于n^loga。因此，总运行时间将f(n)乘以关卡总数。
T(n) = θ(n^loga * logn)哪里k可以>=0。一棵树logn的高度是多少k >= 0。
注意：这里k+1是log in logn的基础
案例3：
让我们假设每个级别上的操作成本在每个级别上都减少了一个显着因素，并且当我们到达叶级别时，值f(n)变得多项式大于值n^loga。那么整体运行时间将主要受第一级成本的支配。因此T(n) = θ(f(n))。
如果您对更详细的阅读和练习示例感兴趣，请访问我的博客条目解决重复的主方法
于 2015-06-19T20:36:06.213 回答
5
我想你误解了它。 如果 n^logba > f(n) 是案例 1 并且 T(n)=Θ(n^logb(a))
在这里你不应该担心 f(n) 结果，你得到的是 T(n)=Θ(n^logb(a))。f(n) 是 T(n) 的一部分。如果你得到结果 T(n)，那么该值将包含 f(n)。所以，没有必要考虑那部分。
如果您不清楚，请告诉我。
于 2012-12-26T21:40:54.100 回答