问题标签 [master-theorem]

最近一直在研究递归；怎么写，怎么分析等等。我一直认为递归和递归是一回事，但是最近的家庭作业和测验中的一些问题让我觉得有细微的差别，“递归”是一种方法描述递归程序或函数。

直到最近，这对我来说都是非常希腊化的，当我意识到有一种叫做“主定理”的东西用来写问题或程序的“递归”时。我一直在阅读维基百科页面，但是，像往常一样，事情的措辞让我真的不明白它在说什么。我通过例子学得更好。

所以，有几个问题：假设你得到了这个重复：

r(n) = 2*r(n-2) + r(n-1);
r(1) = r(2) = 1

这实际上是主定理的形式吗？如果是这样，用语言来说，它在说什么？如果你想写一个小程序或基于这种递归的递归树，那会是什么样子？我是否应该尝试替换数字，查看模式，然后编写可以递归创建该模式的伪代码，或者，因为这可能是主定理的形式，是否有更直接的数学方法？

现在，假设您被要求为从前一次重复创建的程序执行的加法次数查找重复次数 T(n)。我可以看到基本情况可能是 T(1) = T(2) = 0，但我不确定从那里去哪里。

基本上，我问的是如何从给定的重复到代码，反之亦然。由于这看起来像主定理，我想知道是否有一种直接和数学的方法来解决它。

编辑：好的，我已经查看了我过去的一些作业，以找到另一个我被问到的例子，“寻找复发”，这是这个问题的一部分，我在帖子中遇到了麻烦。

以最佳方式描述以下程序片段中加法运算次数的递归（当使用 l == 1 和 r == n 调用时）

在主定理中，如果 f(n) = O(log b of ae) 在案例 1 中，案例 1 和 3，我想知道为什么必须在那里减去常数 e？

在主定理的第三种情况下，必须添加一个常数......为什么会这样？

常数的依据是什么？

在我的中期，我遇到了问题：

我应该使用大师或替代方法找到它的大 theta 符号。所以我所做的是

a = 8, b = 2 k = 3

日志₂ 8 = 3 = k

因此，T(n) 是大 theta n ³。我得了 1/3 分，所以我一定是错的。我做错什么了？

我一直在观看麻省理工学院开放课件网站上的一些视频讲座，在第三节讲座视频中，讲师介绍了递归矩阵乘法，并提出时间复杂度为：

T(n) = Θ(n3)

对我来说很明显，我真的需要复习一些数学，但我真的看不出这个答案和主定理方法提到的任何一个案例之间的联系。我知道递归关系的形式是：
T(n) = a*T(n/b) + f(n)对于 n > 1。
使用这种递归关系：a = 8、b = 2和。f(n) = Θ(n2)

那么，他们是怎么得到的呢？Θ(n3)

他提到了，这是有道理的。但是，我只是无法确定示例递归关系对应于三种情况中的哪一种，使用. log28 = 3f(n)

因为，案例 2 是唯一的f(n) = Θ(anything)，那么我猜就是这样。然而，我想我的问题与对数或指数的属性有关。

如果那么你如何从一个for到一个用例 2？我可能在这里错过了什么？f(n) = Θ(nlog28 * (log2n)k+1)Θ(n3)f(n)Θ(n2)

递归关系

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

（其中 lg 是以 2 为底的对数）可以使用主定理解决，但我不太确定答案。我找到了我的答案，但为了防止信息级联，我没有在这里提及。请帮我找到上面的大 O 和 Ω。

使用主定理来O()限制这个陈述：

T(n) = 16T(n/4) + n2 + log n

我正在尝试越来越多地理解主定理，并尝试在网上找到更多示例并获得他们的解决方案。

= O(n2)使用主定理。

上面的比下面的复杂吗？

两者都使用主定理，但我不知道如何检查常数。O(n2)

我认为这很有趣，但我不确定我的解决方案。该算法计算 x ⁿ

如果我使用主定理，我的推理是这样的

但是在这种情况下 f(n) 是 1？因为 n <= 4 是常数。给我：

如果我使用替代，我会得到这个答案

我觉得我做错了很多事情。有人可以指出我正确的方向吗？

我在这里感到困惑，主定理的哪种情况为这种递归关系找到了紧密的界限：

T(n) = 27T(n/3) + Q(n ³ log n)

这是我的解决方案：
f(n) = n ³ log n
a=27 b = 3 所以

所以我们可以在这里看到f(n) > n ³
所以这个：

案例 3 将适用：如果我在这里错了，请纠正我。
注意：但它的答案是 n ³ log ² n，这是由 Master Theorem 的案例 2 来的。我应该申请哪一个？

假设我有一个像 T(n)=2T(n/4)+1 这样的情况。f(n)=1 a=2 和 b=4。因此n^(1/2)>1。那应该是第一种情况。但是在第一种情况下也有一个 lambda，因此对于某些 lambda >0，f(n)=O(n^((1/2)-lambda))。在这种情况下，lambda 将是 1/2？