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

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)完全按照你的建议定义.经常使用=而不是ε只是滥用符号; 但它很方便,并且在实践中不会引起任何歧义.