algorithm - O(N) 算法如何也是 O(N^2) 算法？

Question

我在读大 O 表示法

So, any algorithm that is O(N) is also an O(N^2).

这让我感到困惑，我知道 Big-O 只给出上限。

但是一个 O(N) 算法怎么可能也是一个 O(N^2) 算法。

有没有这样的例子？

我想不出有什么。

谁能给我解释一下？

Answer 1

“上限”意味着算法花费的时间不超过(即 <= )那么长(因为输入大小趋于无穷大，并考虑了相关的常数因子)。

这并不意味着它实际上会花那么长时间。

O(n) 也是 O(n log n), O(n²), O(n³), O(2 ⁿ) 以及任何其他渐近大于 n 的值。

如果你熟悉相关的数学，你也可以从the formal definition看到这个.