是2 ^(2n)= O(2 ^ n)

Question

Is 2(n+1) = O(2n)?

我相信这个是正确的,因为n+1 ~= n.

---

Is 2(2n) = O(2n)?

这个似乎会使用相同的逻辑,但我不确定.

Answer 1

第一种情况显然是正确的 - 你只需要取消常量

目前对问题第二部分的回答,看起来像是对我的一种解释,所以我会尝试给出正确的数学解释.让我们假设第二部分是真的,那么从big-O的定义,你有:

这显然是错误的,因为没有这样的常数可以满足这种不平等.

Answer 2

声明：2^(2n) != O(2^n)

反证法：

1. 假设：2^(2n) = O(2^n)
2. 这意味着，对于所有 n >= n_0，存在 c>0 和 n_0 st 2^(2n) <= c * 2^n
3. 两边除以2^n，我们得到：2^n <= c * 1
4. 矛盾！2^n 不受常数 c 的限制。

因此 2^(2n) != O(2^n)

Answer 3

注意

2 n+1 = 2(2 n )

和

2 2n = (2 n ) 2

从那里，要么使用您知道的 Big-O 符号规则，要么使用定义。

Answer 4

2 ⁿ⁺¹ = O(2 ⁿ )因为 2 ⁿ⁺¹ = 2 ¹ * 2 ⁿ = O(2 ⁿ )。假设 2 ²ⁿ = O(2 ⁿ ) 则存在一个常数 c，使得对于超过某个 n ₀的 n ，2 ²ⁿ <= c 2 ⁿ。两边除以 2 ⁿ，得到 2 ⁿ < c。_{c 和 n 0}没有任何值可以证明这一点，因此假设为假，并且 2 ²ⁿ != O(2 ⁿ )

Answer 5

我假设您只是省略了左侧的O（）表示法。

O（2 ^（n + 1））与O（2 * 2 ^ n）相同，并且您始终可以提取常数因子，因此它与O（2 ^ n）相同。

但是，恒定因素是您唯一可以采用的方法。2 ^（2n）可以表示为（2 ^ n）（2 ^ n），而2 ^ n不是常数。因此，您的问题的答案是是和不是。