问题标签 [master-theorem]

主定理与T(n) = aT(n/b) + f(n)a >=1 和 b > 1 形式的递归一起使用，在这种情况下，b 的值可以很容易地从递归中看出，但是我有一个形式的递归

我如何得到b？

因此，我使用 Master 定理计算以下函数的平均案例复杂度：

根据http://people.csail.mit.edu/thies/6.046-web/master.pdf问题 7，

它说

不适用（f(n) 和 n ^{log _b a}之间的非多项式差异）

这个答案也支持pdf，说不。

然而，在这个视频中，教练在 12:26 解决了同样的问题，他给出了答案

谁能解释哪一个是错的，为什么？

我请求帮助解释证明是如何工作的。我看过它的例子，但很难理解它。

证明以下

方程的解

T(n) = aT(n/b) + Θ(n ^k log ^p n) 其中 a ≥ 1, b > 1, p ≥ 0

• T(n) = O(n ^{log _b a} ) 如果 a > b ^k

• T(n) = O(n ^k log ^p+1 n) 如果 a = b ^k

• T(n) = O(n ^k log ^p (n)) 如果 a < b ^k

这是问题的屏幕截图，格式更好

这是主定理的推广。

我正在使用树方法推导大师定理，我注意到了一些事情。

所以我们有：

$T(n)=a*T(n/b) + n^c$

由此：我们注意到，树的最后一层将有 $a^(log_b_n)$ 分裂，等于 $n^(log_b_a)$

现在，如果 $a=b$，我在最后一级得到 n 个拆分，这是我在快速排序和合并排序中看到的，如果 a

是否有大于 n 个拆分的实际示例？我们实际上在哪里重复元素的操作？

*此外，数学溢出格式似乎不起作用。如果有人提供帮助，将不胜感激。

当我应用主定理时，我得到 O(n) 但是当我尝试使用递归树来解决它时，我被卡住了，无法找出任何解决方案。

我试过这个：

我该如何解决这个GP？

n幂n（即n^n）是多项式吗？可以 T(n) = 2T(n/2) + n^n用高手的方法解决吗？

Master 定理可以应用于 f(n) 为零的递归，例如：T(n)=2T(n/3) + 0? 如果是，将如何解决？考虑到这一点，它会花费恒定的时间T(1)=1吗？

我有这个复发：

我想应用Master Method因为它似乎属于Case 1，所以我想探讨一下：

但我不知道我该怎么做。我走对了吗？

我最近遇到了一些关于主定理之类的练习。一个要求我们找到一些表达式的 Θ()（给定 Τ(1)=Θ(1)）。大多数都用主定理解决了，但是这个

显然不是这样解决的，因为它不是定理的通用形式。
我们如何找到它的 Θ()？

这是我的递归函数：

xyz() 是 ϴ(n^3)。Master定理在这里有效吗？如果，是，我将如何写？