解决递归问题时，何时需要考虑楼层和上限？

Question

我发现在解决递归问题时有些地方会忽略地板和天花板。

来自CLRS（第4章，第83页）的示例，在这个例子中忽略了地板：

这里（第2页，练习4.1-1）是一个忽略了天花板的例子： （编辑：根据公众意见，这有点可疑。）

事实上，在CLRS（第88页）中提到：

“解决递归问题时，地板和天花板通常不重要.”

我的问题：

1. 这里的“通常”是否意味着所有情况？如果是的话，我可以一直忽略它们。
2. 如果不是，那么在解决递归问题时，什么情况下地板和天花板真正有意义？

注意：这不是一个作业问题。当我刷新我的DS和算法概念时，我想到了这个问题。

- Tejas Patil

---

在你的例子中，它并没有被忽略。 - Oliver Charlesworth

@Oli Charlesworth：是的，这就是我迄今为止看到的被忽略的情况。即使CLRS也提到“通常会被忽略”。我想知道什么时候需要使用floor和ceiling？或者我可以一直忽略它们吗？ - Tejas Patil

此外，这是一个数学问题，不是编程问题。乍一看，地板/天花板被不等式消除的原因是正在研究渐近行为；根本没有解决递归。 - Potatoswatter

@Potatoswatter：我在SO上看到过一些关于递归、大O等算法问题的提问，这些问题并不直接涉及编程。如果这里不是我发布问题的正确地方，你能否建议一个好的地方？ - Tejas Patil

@TejasP http://math.stackexchange.com - Potatoswatter

Answer 1

对于所有的x，地板和天花板函数满足以下不等式：

• x−1 < ⌊x⌋ ≤ x

• x ≤ ⌈x⌉ < x+1

因此，在第一个例子中，我们有⌊n / 2⌋ ≤ n / 2。另外，由于对数是单调递增的函数，我们知道lg ⌊n / 2⌋ ≤ lg(n / 2)。将这些放在一起，我们得到第一个不等式2(c ⌊n / 2⌋ lg ⌊n / 2⌋) + n ≤ cn lg(n / 2) + n。

第二个例子实际上包含一个错误：c lg ⌈n / 2⌉ + 1 从不小于但可以等于 c lg(n / 2) + 1。然而，c lg ⌈n / 2⌉ + 1 ≤ c lg(n / 2 + 1) + 1 是正确的，我们可以通过它来得到一个上界，比如说 c lg(n / 2) + 2（假设 n ≥ 2），从而推导出所需的结论 T(n) ∈ O(lg n)。

事实上，第二个例子还包含其他错误：即使在下面段落中所述的假设条件下（你没有引用），最后一个 = 号也应该是 ≤。

（附注：呼，这真是一件痛苦的事情，没有 LaTeX 就要打这样的内容。这就是为什么像这样的问题最好在 math.SE 上提问的原因之一。）

- Ilmari Karonen

---

@ilmariKaronen：谢谢您的解释。那么我可以说，在使用替换法时，永远不能忽略上限吗？ - Tejas Patil

@TejasP：对于楼层，对于任何单调递增的函数f，都有f（⌊x⌋）≤ f（x）。这不适用于天花板，但我们总是可以使用f（⌈x⌉）≤ f（x + 1）来代替。 - Ilmari Karonen

@lava_07：f(x) = 42 是一个单调递增的函数（虽然不是严格递增）。如果 f 是严格递增的，那么 f(⌈x⌉) < f(x+1) 成立，但如果 f 恰好在从 ⌈x⌉ 到 x+1 的区间内是常数，则 f(⌈x⌉) = f(x+1) 也是可能的。 - Ilmari Karonen

@lava_07：是的，对数函数严格单调递增，至少在数学上定义如此。就我个人而言，我不确定即使考虑到浮点精度不准确性后是否仍然保证这一点，但我怀疑它并非如此。（再说了，使用浮点数，你甚至无法保证 x+1 ≥ x。） - Ilmari Karonen

@lava_07：嗯，x < y 意味着 x ≤ y，所以是的。 - Ilmari Karonen

Answer 2

你提供的两个例子都可以通过主定理进行分析。Akra–Bazzi定理 推广了主定理，并给出了一个足够的条件，即当小扰动可以被忽略时（扰动 h(x) 是 O(x/log² x)），可以应用该定理。对于可由 Akra–Bazzi 进行分析的整数索引递归，您始终可以忽略 floor 和 ceiling，因为它们的扰动最多为 1。

在算法和数据结构的背景下，每个未被 Akra–Bazzi 覆盖的递归都相当奇特。

- oldboy

---

谢谢指出Akra-Bazzi定理，我之前不知道它...那替换法（即忽略floor和ceiling）也可以这么说吗？ - Tejas Patil

如果您的T的猜测单调递增，并且您对上限感到满意，那么您可以始终忽略floor。为了正式处理ceiling，通常需要将T(ceil(...))分析为T(...) + ...，其中第二个...是低阶项。例如，如果您的猜测是T(n) = n^2，则T(ceil(n/2)) ≤ T(n/2 + 1) = T(n/2) + n + 1。不过，实际上，人们可以在算法领域完成整个博士学位而不用用代换法解决单个递归问题。 - oldboy