algorithm - 为什么 O(n^2) 算法在相同输入上比 O(n) 算法运行得更快？

Question

两个算法说 A 和 B 是为解决同一个问题而编写的。算法 A 是 O(n)。算法 B 是 (n^2)。您希望算法 A 的效果更好。

但是，当您运行同一台机器的特定示例时，算法 B 运行得更快。给出理由解释这样的事情是如何发生的？

Answer 1

例如算法A，可以及时运行10000000*n这是 O(n) .
如果算法 B，正在 n*n 中运行这是 O(n^2) , 每 n < 10000000 A 都会变慢.

O(n), O(n^2)是描述 n->infinity 时行为的渐近运行时

编辑 - 示例

假设你有以下两个函数:

boolean flag;

void algoA(int n) {
  for (int i = 0; i < n; i++)
    for (int j = 0; j < 1000000; j++)
      flag = !flag;

void algoB(int n) {
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      flag = !flag;

algoA有n*1000000标志翻转操作所以它是O(n)而algoB有n^2标志翻转操作所以它是O(n^2) .

只解决不等式1000000n > n^2你会得到 n < 1000000它拥有。即 O(n)方法会比较慢。