用O(n^2)写解有时比用O(n)写好吗？[副本]

Question

public void solutionLinear(Problem problem) {
  for (int i = 0; i < problem.getSize(); i++) {
     // do something with problem and compute solution
  }
}

public void solutionQuadric(Problem problem) {
  for (int i = 0; i < problem.getSize(); i++) {
    for (int j = 0; j < problem.getSize(); j++) {
      // do something with problem and compute solution
    }
  }
}

Answer 1

大O复杂度测量省略了常系数，因此“O(N)复杂度”和“O(N^2)复杂度”分别大致对应于“在a*N+b秒内运行”和“在c*N^2+d*N+e秒内运行”。如果A&B较大，C&D&E较小，后者可能更好。

考虑代码示例：

public void solutionLinear(Problem problem) {
  for (int i = 0; i < problem.getSize(); i++) {
     do_stuff_taking_one_hour();
  }
}

public void solutionQuadric(Problem problem) {
  for (int i = 0; i < problem.getSize(); i++) {
    for (int j = 0; j < problem.getSize(); j++) {
      do_stuff_taking_one_second();
    }
  }
}

尽管是O(n^2)，但只要problem.getsize()小于60，后一种算法就会运行得更快。