我们如何比较以下的大0符号，因为它们都是O(X^n)?

Question

我在比较某些大0符号时注意到我们通常忽略常量。这对下面的情况也成立吗?O(5^3n)O(15^n)O(5^n)O(5^3n+5)O(3^5n)

根据假设，所有这些应该是相等的，但是值5,15和3会产生差异吗?

Answer 1

您的断言"我们通常忽略常量";这不是真的。也可能是不完整的

0符号是近似值。

你可以忽略每一个增长较慢的加数。

:

0 (n+4) = 0 (n)

O(n²+ n) = O(n²)

为了避免复杂计算中的复杂演算，不能提供额外的信息来改进算法。