algorithm - 为什么在案例 3 中添加一个常数？

Question

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

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

常数的依据是什么？

Answer 1

你可能会这样想——让我们以第三种情况为例：（
f(n) = O(n^(log(b a) + e)) for e < 0日志不是 (a - e)，而是 (log in base b of a) - e)
这是什么意思？
让我们首先确定一件事：右侧的整个 blob - 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))。
让我们看一下 master 方法所基于的通用形式
T(n) = aT(n/b) + f(n)
：aT(n/b)部分，本质上是循环。决定我们将进行多少次迭代的东西。右侧部分是循环的主体。实际完成的工作。如果右侧对左侧渐近弱，则右侧的影响较小，并且我们有一些可爱的公式来确定渐近行为是否更弱、相等或更大。正如我上面解释的那样，我们减去或添加 e，以确定它是否更大、更小或相等。

用文字而不是我的母语来解释这些事情对我来说有点困难，我希望它能被理解。