问题标签 [master-theorem]

在大师定理中，给出了一个“插件”公式来找到大 O，因为它满足某些条件。

但是，如果我们遇到如下问题怎么办？谁能告诉我如何一步一步地做公式。哪些主题可以帮助我更多地了解这些类型的问题。假设问这个问题的人对归纳一无所知。

我的任务如下：通过使用递归树找到递归的渐近上限的猜测。通过以下方式验证渐近上界：

我该如何处理？我对递归树、替换方法和主定理有一些了解。请帮忙！

我应该使用哪种方法来解决这种复发？

主方法是获得解决方案的直接方法。主方法仅适用于以下类型的重复或可转换为以下类型的重复。

T(n) = a T(n / b) + f(n) 其中 a ≥ 1，b > 1，且 f(n) = Θ(n ^c )。

有以下三种情况：

1. 如果 c < log _b (a) 则 T(n) = Θ(n ^{log _b (a)} )。

2. 如果 c = log _b (a)，则 T(n) = Θ(n ^c log(n))。

3. 如果 c > log _b (a) 则 T(n) = Θ(f(n))。

在 Master Method 中，如果 f(n) 包含 log(n) 的某个项，是否可以通过 Master Method 解决这个问题？例如在 T(n)=4T(n/2)+n^2logn 这里主定理是否适用

假设给你 n 个硬币，其中一些很重，另一些很轻。所有重硬币的重量都相同，所有轻硬币也一样，重硬币的重量严格大于轻硬币的重量。已知至少有一枚硬币很轻。你得到一个天平，你可以用它来衡量一个硬币子集和另一个不相交的硬币子集。展示如何使用 O(log2 n) 称重来确定重硬币的数量。

我正在阅读CLRS(Introduction To Algorithms, 3rd edition)一书，发现 master theorem 的证明似乎有错误。在第 104 页，为了将证明扩展到所有整数，它使用了一个似乎不正确的不等式。书上说：

我们的第一个目标是确定深度 k 使得 nk 是一个常数。使用不等式 [x]<=x+1，我们得到

[x] 这里表示 x 的上限，显然[x] < x+1, 不是[x] <= x+1。此外，在第54页，还有另一个不等式证实了我的想法。

任何人都可以帮助澄清这一点，为什么他们会发生冲突？如果这个不等式不正确，那么整个证明将不正确

我正在分析这段代码以查看如何计算最坏情况下的理论运行时间。我正在使用主定理。有人可以给我一个关于如何到达运行时间的分步解决方案吗？

我只是在尝试掌握 Master Theorem，当我尝试评估 T(n) = T(n/2) + n 时有点困惑。使用主定理，答案计算为 O(n)。

但只需通过以下代码：

上述代码的递归方程为 T(n) = T(n/2) + n。因此，上述程序的时间复杂度必须为 O(n)。

但是如果你从逻辑上思考，程序运行的次数是：n+n/2+n/4+n/8+...... = nlogn。因此，从逻辑上讲，上述程序的时间复杂度必须是 O(nlogn)。

我现在很困惑。有人可以帮我解决我哪里弄错了吗？

n⋅log(n) 在 Θ(n) 中吗？
我问这个是因为我正在使用主定理解决重复问题。

方程为 T(n) = 2T(n/2) + n log n

该解决方案表示它满足案例 2，即 T(n) = Θ(n log(n))。

我不明白 n log(n) 怎么可能是 O(n)，当 n > 10 时 n log(n) 不应该大于 n 吗？

可以应用主定理吗？

或者说 for T (n) = 2T (n/16) + n log n，这里如何应用主定理？

我得到了a = 2，b = 16我不确定cand k。