为什么情况3要加一个常数呢？
在主定理中，情况1和情况1 3 你有 if f(n) = O(log b of ae) 在情况 1 中，我想知道为什么必须减去那里的常数 e ？
在主定理的第三种情况中，必须添加一个常数……为什么会这样呢？
常数是基于什么？
In the Master Theorem, cases 1 & 3 you have if f(n) = O(log b of a-e) in case 1, I wondered why one has to subtract the constant e there?
In the third case of the master theorem one has to add a constant... Why is that so?
What is the constant based on?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您可能会这样想 - 让我们以第三种情况为例：
f(n) = O(n^(log(ba) + e)) 对于 e
0（日志不是 (a - e)，而是 (以 a 的 b 为基数的日志) - e)这是什么意思？
让我们首先确定一件事：右侧的整个斑点 - O(n^(log(ba)))。本质上，这是 T(n) 函数的渐近行为，而不考虑其中的 f(n) 部分。
这部分并不完全直观，但仔细想想，你就会发现它是正确的。 （只需计算 f(n) = O(1) 的一些值，您就会发现我是对的。因为不存在的 f(n) 无论如何都是 O(1)。）
因此，鉴于此，我们看看e。 e 有什么作用？它肯定低于零，我们知道，由于我们对其施加的约束，这意味着当将 e 放入方程时，它会降低渐近“类”（如 n^2、log n 等） 。换句话说，如果您可以降低
aT(n/b)部分的渐近类并使其等于f(n)，那么这意味着aT(n/b)渐近大于 f(n)，我们相应地采取行动。这意味着什么，以及主方法的全部内容，就是解决以下问题：O(T(n) - f(n)) = O(f(n))。
让我们看看主方法所基于的通用形式：
T(n) = aT(n/b) + f(n)aT(n/b)部分本质上是循环。决定我们将进行多少次迭代的事情。右侧部分是循环体。实际完成的工作。如果右侧渐近弱于左侧，则右侧的影响较小，并且我们有一些可爱的公式来确定渐近行为是否更弱、相等或更大。我们按照上面的解释对 e 进行减法或加法，看看它是更大、更小还是相等。对我来说，用文字而不是用我的母语来解释这些事情有点困难，我希望它能被理解。
You might think of it this way - lets take the third case as an example:
f(n) = O(n^(log(b a) + e)) for e < 0(The log is not of (a - e), but rather it's (log in base b of a) - e)What does this mean?
Lets establish one thing first: The entire blob at the right side - O(n^(log(b a))). This is, in essence, the asymptotic behaviour of the T(n) function, without taking into account the f(n) part of it.
This part is not perfectly intuitive, but think about it, and you'll see its correct. (Just calculate some values for f(n) = O(1) and you'll see I'm right. Since nonexistant f(n) is, for all intents and purposes, O(1).)
So, given that, we look at the e. What does the e do? It's lower than zero for sure, we know that thanks to the constraints we put on it, so that means the e will lower the asymptotic "class" (as in, n^2, log n, etc.) when put in the equation. In other words, if you can lower the asymptotic class of the
aT(n/b)part and make it equal to f(n), then that meansaT(n/b)is asymptotically bigger than f(n), and we act accordingly.What this means, and what the master method is all about, is solving the following: O(T(n) - f(n)) = O(f(n)).
Lets look at the generic form the master method is based upon:
T(n) = aT(n/b) + f(n)The
aT(n/b)part, is in essence the loop. The thing that decides how many iterations we will have. The right part, is the body of the loop. The actual work done. If the right side is asymptotically weak to the left side, than the right side matters less, and we have some lovely formulas to decide the asymptotic behaviour if its weaker, equal or bigger. We substract or add the e as I explained above, to find out if it's bigger, smaller or equal.It's a bit hard for me to explain these kinds of things in text and not in my native language, I hope it was understood.