algorithm - 为什么 "="用于表示算法的时间复杂度而不是 "∈"？

Question

我在这里使用 big-o。设 f(n) 和 g(n) 是两个具有相同时间复杂度且等于 O(n) 的函数。

根据定义(当使用“=”来解释时间复杂度时)这种推理可能是正确的:

IF f(n)=O(n) AND g(n)=O(n) THEN f(n)=g(n)

但正如我们所知，具有相同增长率的两个函数并不一定相同。

为了避免这种不匹配，为什么不将 O(n) 定义为任何时间复杂度为 O(n) 的函数的集合？

O(n)=O(f(n))=O(g(n))={n, f(n), g(n), ...}
f(n)∈O(n)
g(n)∈O(n)

Answer 1

O(n) 实际上完全按照您的建议定义。频繁使用 = 而不是 ∈ 只是对符号的滥用；但它很方便，并且在实践中不会造成任何歧义。