time-complexity - 使用大 O 表示法的复杂性描述有效形式

Question

根据wiki，我们应该以下列方式使用 Big O 表示法：

f(n) = O(g(x))

where=不是读作“等于”，而是读作“是”。

因此，这意味着如果算法具有复杂性，例如n^2 + 2n + 5，我们应该将其记为：

n^2 + 2n + 5 = O(n^2)

但在一些文章中，我看到人们将复杂性描述为：

O(n^2 + 2n + 5) = O(n^2)反而

那么后一种表达方式是有效形式还是我们不能那样记呢？

标签： time-complexitybig-ocomplexity-theory

Answer 1

实际上，O(g(x)) 是一个集合，它应该用集合符号 f(x) \in O(g(x)) 来写。

作者通常会提到这一点，并说为简单起见，我们将为此使用 =。