问题标签 [master-theorem]

问题是 ：

我不确定主定理是否在这里有效，并且有点卡住了。

这个公式是主定理的案例 2

a = 2; b = 2; (f(n) = 3^1) ?

所以 logba = 1 和 c = 1 在这种情况下是主定理情况 2 吗？还是我应该忽略常数 3。

您如何计算这些关系的紧密约束运行时间？

• T(n)=T(n-3)+n^2
• T(n) = 4T(n/4)+log^3(n)

对于第一个，我使用了给我 n^2 但不正确的替换方法，第二个我使用了 Masters Theorem 并得到了 nlog^4(n)，这也是不正确的。一个彻底的解释会很有帮助。谢谢！

对于关系

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

我可以先求解给出 O(n^2) 的项 (T(n-1) + n)，然后求解项 T(n/2) + O(n^2) 吗？

根据也给出 O(n ^ 2) 的主定理还是错误的？

在学习Master theorem时，我无法想出一个真实世界的算法作为示例，其递归策略将属于Case 3。您能否建议任何链接，我可以在其中阅读有关此类算法的更多信息？

我目前正在尝试解决与主定理的这种关系：

T(n) = 2T(n/4) + log n

我已经计算出 a = 2 和 b = 4，但我对 log n 感到困惑。

我的脚本说：c(n)（这里是 log n）是 Big O(n^d) 的元素。

如果我能在这里算出我的 d，我会比较 a 和 b^d 来找出我的主定理案例。

但是，由于它在这里是 log n，我不确定它的 Big O 表示法。

我的意思是我可能会说它是 O(n ^1/2 ) 的元素，然后会导致情况二，其中 a 和 b^d 相同，但它也是 O(n ¹ ) 的元素，然后是又是一个案例。

我正在做一些功课，我正在努力解决一个特定的问题。我的作业中有一个类似的问题，所以我需要掌握这个问题。

这是代码：

我有基本情况，我认为它是0，n=1； 然而，到达T(n)是我苦苦挣扎的地方。

它需要类似T(n-1)+c，n>1。

我需要用递归公式来表达代码。

任何人都可以为我 ELI5 吗？

现在要计算这个问题的复杂性，我们必须使用减法主定理。现在我推导出了结果为的递归关系T(n)=c+3T(n-1)。n>1但是如何使用减法主定理计算这个问题的复杂性，因为在主定理f(n)=O(n^d)中 d>0 .但是这里是c，它是一个常数项，而不是格式O(n^d)。那么如何解决这个问题呢？

我有找到复杂性的主定理，但问题是主定理说

对于形式的重复

有以下三种情况： /******************logba 表示 a 以 b 为底的 log ******************/

1. If f(n) = Θ(n^c) where c < Logba then T(n) = Θ(nLogba)

2. If f(n) = Θ(n^c) where c = Logba then T(n) = Θ(ncLog n)

3. If f(n) = Θ(n^c) where c > Logba then T(n) = Θ(f(n))

现在解决我的问题

我的解决方案和c = 2with as So 在这种情况下它会下降，复杂性是什么logba = log21base = infinity

你好 ！！我试图找到解决此问题的信息和示例，但找不到。这是我的考试准备问题，而不是作业。有人可以解释解决此问题的步骤吗？而且，任何具有此类相关示例的资源？干杯！！