algorithm - 当函数中有一个 ceil 时，如何找到渐近复杂度？ (2^(2^ceil(log2(n)))) = O( 2^n )?

Question

我运行了一个程序来找出 n + 1 和 2**ceil(log2(n+1)) 之间的区别，其中 n 是 2 的幂。一直呈指数增长

所以根据 Big - O 的定义，不存在满足 -

的常量 c'

2^(2^ceil(log2(n))) <= c' * 2^n

因此

(2^(2^ceil(log2(n)))) != O( 2^n )

以上说法正确吗？如果是，那我怎么证明呢？

Answer 1

我们需要证明，对于每个常数 c，存在 n 使得 2^(2^ceil(log2(n))) > c * 2^n。对于某个整数 k > 1，我们只考虑 n = 2^k + 1；这是我们的权利，因为我们不是要证明所有 n 的命题。期望的不等式变为

2^(2^ceil(log2(2^k + 1))) >? c * 2^(2^k + 1).

我们简化了左侧。

ceil(log2(2^k + 1)) = k + 1
2^(2^ceil(log2(2^k + 1))) = 2^(2^(k + 1)).

期望的不等式是

2^(2^(k + 1)) >? c * 2^(2^k + 1).

这个不等式等价于

2^(2^(k + 1) - 2^k - 1) = 2^(2^k - 1) >? c.
2^k - 1 >? log2(c)
2^k >? log2(c) + 1
k >? log2(log2(c) + 1).

k(以及 n)的选择现在很明显；通过不等式向后计算以显示所需的不等式，因此该函数不是 O(2^n)。