当函数中有一个 ceil 时，如何找到渐近复杂度？ (2^(2^ceil(log2(n)))) = O( 2^n )?
How to find asymptotic complexity when the function has a ceil in it ? (2^(2^ceil(log2(n)))) = O( 2^n )?
我 运行 一个程序，用于查找 n + 1 和 2**ceil(log2(n+1)) 之间的差异，其中 n 是 2 的幂。一直呈指数增长
所以根据大-O的定义，不存在满足-
的常量c'
2^(2^ceil(log2(n))) <= c' * 2^n
因此
(2^(2^ceil(log2(n)))) != O( 2^n )
以上说法正确吗？如果是，那我怎么证明呢？
我们需要证明，对于每个常量 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).
a^(a^syl(l(n))) < a^(a^(l(n)+1)) = a^(n)
我 运行 一个程序，用于查找 n + 1 和 2**ceil(log2(n+1)) 之间的差异，其中 n 是 2 的幂。一直呈指数增长
所以根据大-O的定义，不存在满足-
的常量c'2^(2^ceil(log2(n))) <= c' * 2^n
因此
(2^(2^ceil(log2(n)))) != O( 2^n )
以上说法正确吗？如果是，那我怎么证明呢？
我们需要证明，对于每个常量 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).
a^(a^syl(l(n))) < a^(a^(l(n)+1)) = a^(n)