O(N) 算法如何也是 O(N^2) 算法？
How is O(N) algorithm also an O(N^2) algorithm?
我正在阅读大 O 表示法
So, any algorithm that is O(N) is also an O(N^2).
这让我感到困惑，我知道 Big-O 只给出上限。
但是复杂度O(N)的算法怎么可能也是复杂度O(N^2)的算法呢
有没有这样的例子？
想不出。
谁能给我解释一下？
big-O的定义：
某些函数 f(x) 是 O(g(x)) 当且仅当 |f(x)| <= M|g(x)| 对于所有 x >= x0。
显然如果 g1(x) <= g2(x) 那么 |f(x)| <= M|g1(x)| <= M|g2(x)|。
Big-O 表示法描述了上界，但是说 O(n) 也是 O(n^2) 并没有错。 O(n) 算法是 O(n^2) 算法的子集。同样，正方形是所有矩形的子集，但不是每个矩形都是正方形。因此从技术上讲 O(n) 算法是 O(n^2) 算法是正确的，即使它不精确。
对于某事是O(N)，这意味着对于大N，它小于函数f(N)=k*N对于一些固定的k。但它也小于 k*N^2。所以 O(N) 意味着 O(N^2)，或者更一般地，对于所有 m>1.
O(N^m)
*我假设N>=1，对于大N确实是这样。
"Upper bound" 表示算法花费 不超过 （即 <=）那么长（因为输入大小趋于无穷大，具有相关的常数因子考虑过）。
这并不意味着它真的会花那么长时间。
O(n) 也是 O(n log n)，O(n2)，O(n3 ), O(2n) 以及任何其他渐近大于 n.
如果你熟悉相关的数学，你也可以从the formal definition看到这个。
O 表示法可以天真地读作 "less than".
在数字中，如果我告诉你 x < 4 那么显然 x<5 和 x< 6 等等。
O(n) 意味着，如果算法的输入大小为 n（n 可以是元素的数量，或者元素的大小或任何其他以数学方式描述输入大小的东西），那么算法运行 "about n iterations".
更正式的意思是算法中的步数x满足：
x < k*n + C 其中 K 和 C 是正实数
换句话说，对于所有可能的输入，如果输入的大小为n，那么算法最多执行k*n + C步。
O(n^2) 类似，除了边界是 kn^2 + C。因为 n 是自然数 n^2 >= n，所以定义仍然成立。的确如此，因为 x < kn + C 那么 x < k*n^2 + C.
所以一个O(n)算法是一个O(n^2)算法，一个O(N^3算法)和一个O(n^n)算法等等。
对于只有一个循环的算法，复杂度为 O(n)，而嵌套循环的算法，复杂度为 O(n^2)。
现在考虑其中使用嵌套循环的冒泡排序算法，
如果我们将一组已经排序的输入提供给冒泡排序算法，则内部循环将永远不会执行，因此对于这样的场景，它的复杂度为 O(n)，而对于其他情况，它的复杂度为 O(n^2) ).
我正在阅读大 O 表示法
So, any algorithm that is O(N) is also an O(N^2).
这让我感到困惑，我知道 Big-O 只给出上限。
但是复杂度O(N)的算法怎么可能也是复杂度O(N^2)的算法呢
有没有这样的例子？
想不出。
谁能给我解释一下？
big-O的定义：
某些函数 f(x) 是 O(g(x)) 当且仅当 |f(x)| <= M|g(x)| 对于所有 x >= x0。
显然如果 g1(x) <= g2(x) 那么 |f(x)| <= M|g1(x)| <= M|g2(x)|。
Big-O 表示法描述了上界，但是说 O(n) 也是 O(n^2) 并没有错。 O(n) 算法是 O(n^2) 算法的子集。同样，正方形是所有矩形的子集，但不是每个矩形都是正方形。因此从技术上讲 O(n) 算法是 O(n^2) 算法是正确的，即使它不精确。
对于某事是O(N)，这意味着对于大N，它小于函数f(N)=k*N对于一些固定的k。但它也小于 k*N^2。所以 O(N) 意味着 O(N^2)，或者更一般地，对于所有 m>1.
O(N^m)*我假设N>=1，对于大N确实是这样。
"Upper bound" 表示算法花费 不超过 （即 <=）那么长（因为输入大小趋于无穷大，具有相关的常数因子考虑过）。
这并不意味着它真的会花那么长时间。
O(n) 也是 O(n log n)，O(n2)，O(n3 ), O(2n) 以及任何其他渐近大于 n.
如果你熟悉相关的数学，你也可以从the formal definition看到这个。
O 表示法可以天真地读作 "less than".
在数字中，如果我告诉你 x < 4 那么显然 x<5 和 x< 6 等等。
O(n) 意味着，如果算法的输入大小为 n（n 可以是元素的数量，或者元素的大小或任何其他以数学方式描述输入大小的东西），那么算法运行 "about n iterations".
更正式的意思是算法中的步数x满足：
x < k*n + C 其中 K 和 C 是正实数
换句话说，对于所有可能的输入，如果输入的大小为n，那么算法最多执行k*n + C步。
O(n^2) 类似，除了边界是 kn^2 + C。因为 n 是自然数 n^2 >= n，所以定义仍然成立。的确如此，因为 x < kn + C 那么 x < k*n^2 + C.
所以一个O(n)算法是一个O(n^2)算法，一个O(N^3算法)和一个O(n^n)算法等等。
对于只有一个循环的算法，复杂度为 O(n)，而嵌套循环的算法，复杂度为 O(n^2)。 现在考虑其中使用嵌套循环的冒泡排序算法，
如果我们将一组已经排序的输入提供给冒泡排序算法，则内部循环将永远不会执行，因此对于这样的场景，它的复杂度为 O(n)，而对于其他情况，它的复杂度为 O(n^2) ).