我在这里使用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)