为什么在案例3中添加了一个常量？

Question

在Master Theorem，案例1 & 3如果f（n）= 0（情况1中的log b），我想知道为什么必须在那里减去常数e？

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

什么是常数基于？

Answer 1

你可能会这样想的吧 - 让我们的第三种情况为例：
f(n) = O(n^(log(b a) + e)) for e < 0（日志不是的（A - E），而是它（登录的基极b） - E）
这是什么意思？
让我们先确定一件事：整个blob在右侧 - O（n ^（log（b a）））。这实质上是T（n）函数的渐近行为，而不考虑它的f（n）部分。
这部分不是很直观，但想一想，你会看到它的正确。 （只要计算f（n）= O（1）的某些值，你就会看到我是正确的。因为对于所有的意图和目的，不区分的f（n）是O（1）。）

，鉴于此，我们看看e。 e做什么？它肯定低于零，我们知道，由于我们对它的约束，所以这意味着当将等式放入等式中时，e将降低渐近“类”（如in，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，以确定它是更大，更小还是相等。

我很难用文字解释这些东西，而不是用我的母语解释，我希望能够理解。