time-complexity - 对于时间复杂度（指数情况），Big O 中可以忽略哪些常数？

Question

显而易见的是线性项上的常数，例如 2n、4n 和 8n 都只是 n 或 O(n)。

但是指数常数1.6^n和2^n呢？在这种情况下，常数似乎对时间复杂度有更大的影响。

此外，对于指数时间复杂度而言，也没有真正方便的方法来编写全部内容。

O(K^n)也许。

在这个备忘单中，他们似乎使用O(2^n)是否意味着所有指数复杂性都应该这样写？

可能不是。

标签： time-complexitybig-o

Answer 1

2n、4n 和 8n 都只是 O(n) 是对的，而且 O(1.6 ⁿ ) 与 O(2 ⁿ ) 不同也是对的。要理解为什么，我们需要参考大 O 符号的定义。

符号 O(...) 表示一组函数。一个函数 f(n) 在集合 O(g(n)) 中当且仅当对于某些常数 c 和 n _{0 ，当 n ≥ n 0}时我们有f(n) ≤ c * g(n)。鉴于此定义：

• 函数 f(n) = 8n 在集合 O(n) 中，因为如果我们选择 c = 8 和 n ₀ = 1，对于所有 n ≥ 1 ，我们有8n ≤ 8 * n 。
• 函数 f(n) = 2 ⁿ不在集合O(1.6 ⁿ ) 中，因为无论我们选择c 和 n ₀中的哪一个，对于一些足够大的 n ， 2 ⁿ > c * 1.6 ^{n 。}我们可以选择 n > log ₂ c + n ₀ log ₂ 1.6 作为具体的反例。
• 但是请注意，f(n) = 1.6 ⁿ 在集合 O(2 ⁿ ) 中，因为对于所有 n ≥ 1，1.6 ⁿ ≤ 1 * 2 ^{n 。}

对于编写指数复杂度的“包罗万象”方式，您可以编写 2 ^O(n)。这包括具有任意基数的指数函数，例如函数 f(n) = 16 ⁿ因为这等于 2 ⁴ⁿ，并且 4n 在集合 O(n) 中。这是对符号的滥用，因为在这种情况下，将数字 2 提高到一组函数的幂并没有真正意义，但它很常见，可以理解。