math - 主定理证明中的问题

Question

我正在阅读CLRS(Introduction To Algorithms, 3rd edition)一书，发现 master theorem 的证明似乎有错误。在第 104 页，为了将证明扩展到所有整数，它使用了一个似乎不正确的不等式。书上说：

我们的第一个目标是确定深度 k 使得 nk 是一个常数。使用不等式 [x]<=x+1，我们得到

[x] 这里表示 x 的上限，显然[x] < x+1, 不是[x] <= x+1。此外，在第54页，还有另一个不等式证实了我的想法。

x -1 <  flooring(x) <= x <= ceiling(x) < x+1

任何人都可以帮助澄清这一点，为什么他们会发生冲突？如果这个不等式不正确，那么整个证明将不正确

Answer 1

分为两种情况：

1. [x] > x---> [x] < x+1（微不足道，我认为你同意）
2. [x] = x---> [x]+1 = x + 1--->[x] < x+1

同样对于x-1 < floor(x)，分为两种情况：

1. floor(x) < x--->floor(x) > x-1
2. floor(x) = x---> floor(x) - 1 = x - 1--->floor(x) > x-1

因此，在最后一个等式中 - 剩下的就是floor(x)<=c<=ceil(x)- 这几乎直接来自他们的定义，并且从上述两个声明中我们得到：

x -1 <  flooring(x) <= x <= ceiling(x) < x+1