algorithm - 在解决重复问题时，地板和天花板何时重要？

Question

在解决重复问题时，我遇到了忽略地板和天花板的地方。

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

这里（第 2 页，练习 4.1-1）是一个忽略上限的示例：（ 编辑：我从公众舆论中得知这有点可疑。）

事实上，在CLRS ( pg.88 ) 中提到：

“解决重复问题时，地板和天花板通常无关紧要”

我的问题：

1. 这里的“通常”是指所有情况吗？如果是的话，我可以一直忘记它们。
2. 如果不是，那么在解决重复问题时，地板和天花板何时真正重要？

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

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 )。

事实上，第二个示例也包含其他错误：即使使用以下段落中所述的假设（您没有引用），最后一个 = 符号应该是 ≤。

（Ps. 唷，没有 LaTeX 打字真的很痛苦。这就是为什么最好在math.SE上问这些问题。）

Answer 2

您的两个示例都可以通过主定理进行分析。Akra-Bazzi 定理概括了主定理，并给出了何时可以忽略小扰动的充分条件（扰动 h(x) 为 O(x/log 2 ^x )）。对于 Akra–Bazzi 可分析的整数索引递归，您可以始终忽略地板和天花板，因为它们的扰动最多为 1。

Akra-Bazzi 未涵盖的每一个重复在算法和数据结构的背景下都非常奇特。