math - 标量在大 O 表示法中重要吗？

Question

标量是否包含在大 O 表示法中，或者 O(2n) 实际上与 O(n) 相同，因为没有考虑标量？如果是这样，这是为什么？

Answer 1

Big-O 符号由于其定义而忽略了常数因子（标量）：

f(n) = O(g(n)) 当且仅当存在一个自然数 n ₀和实数 c 使得对于任何自然数 n > n ₀，|f(n)| ≤ |cg(n)|

所以现在假设 f(n) = O(k × g(n))。这意味着有一些自然数 n ₀和实数 c 使得对于任何 n > n ₀，我们有 |f(n)| ≤ |c × k × g(n)|。

我们将使用它来证明 f(n) = O(g(n))。为此，请选择 n ₀作为自然数，选择 c × k 作为实数。然后对于任何 n > n ₀，我们有 |f(n)| ≤ |(c × k) × g(n)|，所以 f(n) = O(g(n))。

希望这可以帮助！