O（N）算法又如何是O（N ^ 2）算法？

Question

我在读有关Big-O符号的信息

因此，任何O（N）的算法也是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 的东西。

如果您对相关数学感到满意，您也可以从正式定义中看到这一点。

Answer 2

O 符号可以天真地读作“小于”。

在数字上，如果我告诉你 x < 4 那么显然 x<5 和 x<6 等等。

O(n) 意味着，如果算法的输入大小是 n（n 可以是元素的数量，或者元素的大小或任何其他数学上描述输入大小的东西），那么算法运行“大约 n迭代”。

更正式地说，它意味着算法中的步数 x 满足：

x < k*n + C 其中 K 和 C 是正实数

换句话说，对于所有可能的输入，如果输入的大小为 n，则算法执行不超过 k*n + C 步。

O(n^2) 是相似的，除了边界是 k n^2 + C。由于 n 是自然数 n^2 >= n 所以定义仍然成立。确实如此，因为 x < k n + C 那么 x < k*n^2 + C。

所以一个 O(n) 算法是一个 O(n^2) 算法，一个 O(N^3 算法) 和一个 O(n^n) 算法等等。