问题标签 [master-theorem]

运行时间是多少？

我的猜测 T(n) = T(n/2) + 1，然后使用主定理。

这个功能怎么样：

这是我的猜测。

T(n) = nT(n/2) + 1

我对此感到非常沮丧。

在 CLRS 第 3 版第 95 页（第 4.5 章）中，它提到像

T(n) = 2T(n/2) + n lg n

无法用主定理解决，因为差异

f(n)/n^(log_b(a)) = (n lg n)/n^1 = lg n

不是多项式。

但是后来我遇到这样的页面，在页面底部，它提到了完全相同的重复，并说它可以用主定理解决，因为它属于“扩展案例 2”，即使差异是非多项式。它变成n lg^2 n（将日志因子增加f(n)一）。

然后我遇到这样的页面，在示例 (e) 中似乎是扩展案例 2 的明确应用（重复出现T(n) = 4T(n/2) + n^2 lg n），但解决方案不是n^2 log^2 n，而是n^2 log n！是我错了还是论文错了？

任何人都可以澄清矛盾并明确说明何时可以使用主定理，何时不能使用？多项式差分检查何时重要，何时不重要？扩展案例 2 是否可用，或者它实际上违反了什么？

编辑：

我尝试直接从第二篇论文中解决递归（e），我得到：

T(n) = n^2 lg^2(n)/2 + n^2 lg(n)/2

这不是大θn^2 lg^2 n吗？

我知道它可以用主方法解决，但如何解决？请帮忙 ？

运行时间的递推关系 T(n) 是什么，为什么？

主定理是否假设 T(1) 是常数？假设我有一个时间复杂度的算法：T(n) = 2T(n/2) + O(1) and T(1) = O(logn)，这个算法的时间复杂度是多少？

我得到一个递归 T(n) = 3T(n/2) + n^2 lg(n)

是否可以使用主定理找到 T(n) = theta(f(n))？有 f(n) 的多对数函数，但据我所知，第 4 种情况是有限的。第四种情况在这里适用吗？

我通常看到两个版本的 Master 定理。

版本 1：

（来自Tim Roughgarden 的课程）

对于形式的递归关系，

有3个案例，

版本 2：

（来自CLRS）

对于形式的递归关系，

有3种情况：

问题： 应该支持哪个版本，为什么？

T(n)=4t(n/2) + n^2 和 t(1)=1

我不知道伙计们，我可以解决其他问题，但我似乎卡住了，无法从这个开始

任何人都可以用以下等式帮助解决分而治之算法的递归关系吗？我很确定你不能在这里使用主定理，因为它不是 T(n/b) 的形式，但可能在这里忘记了一个简单的数学规则。请帮忙。

T(n)=T(√n)+logn。

MIT讲义中的问题1.8是上述递归 http://courses.csail.mit.edu/6.046/spring02/handouts/mastersol.pdf

讲义中的解决方案是 T(n) = Θ(n^lg5)（案例 1）。我没有得到任何满足案例 1 条件的 epsilon 值。请帮我解决这个问题。