O(N)算法又如何是O(N ^ 2)算法? [英] How is O(N) algorithm also an O(N^2) algorithm?

问题描述

我正在阅读有关Big-O符号

I was reading about Big-O Notation

因此，任何O(N)的算法也是O(N ^ 2).

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

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

It seems confusing to me, I know that Big-O gives upper bound only.

但是O(N)算法又如何也可以是O(N ^ 2)算法.

But how can an O(N) algorithm also be an O(N^2) algorithm.

有什么例子吗?

我想不起来.

有人可以向我解释吗?

推荐答案

上限"表示算法花费时间不超过(即< = )那么长时间(由于输入大小趋于无穷大，并考虑了相关的恒定因素).

"Upper bound" means the algorithm takes no longer than (i.e. <=) that long (as the input size tends to infinity, with relevant constant factors considered).

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

It does not mean it will ever actually take that long.

O(n)也是O(n log n)，O(n ² )，O(n ³ )，O(2 ⁿ )以及其他渐近大于n的其他值.

Something that's O(n) is also O(n log n), O(n²), O(n³), O(2ⁿ) and also anything else that's asymptotically bigger than n.

如果您熟悉相关数学，还可以从形式定义.

If you're comfortable with the relevant mathematics, you can also see this from the formal definition.

这篇关于O(N)算法又如何是O(N ^ 2)算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！