algorithm - 证明 2^(na) = O(2^n)？

Question

如何证明 2^(n+a) 是 O(2^n)？我唯一能想到的是 2^n 中的 n 是任意值，因此 n+a 也是任意值，因此 n+a = n。或者，2^(n+a) = 2^n * 2^a。2^n显然是O(2^n)，而a在2^a中作为任意值存在，所以2^a = 2^n = O(2^n)。是否有更清晰/更正式的方式来证明这一点？

Answer 1

对于 big-O 的正式定义，必须存在一个 M 和 n0 使得 2^(n+a) <= M*2^n 对于所有 n > n0。

如果我们选择 M = 2^a，并且 n0 = 0，那么我们可以看到 2^(n+a) = 2^a * 2^n = M*2^n，即 <= M*2^n对于所有 n > n0。因此，2^(n+a) 是 O(2^n)

Answer 2

请参阅此处的大 O 表示法的定义。想想你是否能找到M定义中的常量。

Answer 3

一般来说，要证明f(n)是O(g(n))，您必须找到一个正整数N，使得对于所有n >= N，f(n) <= g(n)。