问题标签 [master-theorem]

我正在尝试解决递归关系以找出我编写的算法的复杂性。这是等式。。

T(n) = T(n-1) + Θ(n)

我找到了 O(n2) 的答案，但我不确定我是否做对了。有人可以确认吗？

更新：如果方程是 T(n) = T(n-1)+Θ(nlogn) 怎么办？它仍然是O（n2）吗？

我只是想验证一些事情我是否执行了以下步骤？

我在步骤 A 中遇到了问题，我最终的 c 范围是：

c >= 1 表示上限 0 < c <= 1 表示下限

将 cn + n 结合起来有什么特殊原因吗？我可以看到它背后的逻辑，但有必要做那一步吗？因为那样我可以在任何情况下都这样做......这有点奇怪......

需要帮助找到解决以下问题的方法：
给予所有人。 并给出. 解决 我尝试了主定理，但所有 3 种情况都不适合这里，我的猜测是使用替换方法，但我不确定如何应用它f(n)9f(n/3)+(n2)*(log3n)n > 1
f(1)=1
f(n)

我知道递归关系的公式是 T(n)=aT(n/b)+f(n)。鉴于这个方程，我知道如何求解 BigO。我的作业问题要求我编写一个递归函数来计算列表中的节点数，我这样做了，但后来要求我编写一个递归关系。这是我的代码：

但是我完全不知道如何创建/制定我自己的递归关系公式......我如何找到a或b......我不知道从哪里开始。如何编写此函数的递归关系？谢谢你。

大师方法——为什么不能解决T(n) = 4*T(n/2) + (n^2)/logn？

我意识到它可以解决类型 T(n) = aT(n/b) + f(n) 的重复

在 MIT OCW 上，他们提到它无法解决上述重复出现的问题。有人可以解释为什么吗？

假设我有一个案例

那应该是第一种情况，因为n^(1/2)>log(n). 在案例 1 中还有一个 lambda f(n)=O(n^((1/2)-lambda)。这个对吗？我怎样才能找到这个 lambda？

我们能解决这个 T(n) = 2T( n/2 ) + n lg n递归方程主定理吗？我来自一个链接，他说我们不能在这里应用主定理，因为它不满足任何 3ree 案例条件。另一方面，他采取了另一个例子 T(n) = 27T(n/3) + Θ(n^3 lg n) 并找到了封闭的解决方案theta(n^3logn) 为了解决这个问题，他使用了主定理的第二种情况If f(n) = Θ(nlogba (lg n)k ) then T(n) ∈ Θ(nlogba (lg n)k+1) for some k >= 0 在这里我产生了困惑，为什么我们不能在这里应用第二种情况，而它完全适合第二种情况。 我的想法： a = 2 , b =2; let k =1 then f(n) = theta(n^log_2 2 logn) for k= 1 so T(n) = theta(nlogn) 但是正如上面提到的我们不能应用主定理我很困惑为什么不.

注意：这是由于 f(n) bcz in和 in * * 如果我在这里错了，请纠正我。T(n) = 2T( n/2 ) + n lg n f(n) = nlog nT(n) = 27T(n/3) + Θ(n^3 lg n)f(n) = theta(n^3log n)

这是关于算法分析：比如说，一个问题的运行时间是：

现在，这是THETA(log base3 n)

但是，如果我使用主方法，我评估为THETA(log base2 n)，使用案例 II

我应该如何从主方法中得到正确的答案？

我正在学习 Master Theorem 的期中考试，并且遇到了 k > 0 的情况 2 的示例。我了解有关该定理的所有内容，除了常数以及它如何递增或计算。

案例 2状态：T(n) = Θ(n ^{log _b a} log ^k+1 n) 当 n ^{log _b a} = f(n) 但 k 来自哪里？

有问题的例子：

矩阵乘法

已发现加法的跨度为：Θ(log n)

在计算乘法的跨度时，示例说明：

M1(n) = M1(n/2) + A1(n) + Θ(1)

A1(n) 真的是 Θ(log n)：M1(n) = M1(n/2) + Θ(log n)

n log _b a = n log ₂ 1 = 1 --> f(n) = Θ(n ^{log _b a} log ¹ n)

所以跨度最终是：Θ（log ² n）。

我想知道为什么在这个例子中 k = 1？

通用形式：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呢？什么时候适用？