为什么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),A将是每较慢n < 10000000.

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)方法会更慢.