与 O-notation 的算法比较

Question

我们考虑解决相同问题的两种算法，Algo1 和 Algo2 问题。对于大小为 n 的任何输入，Algo1 需要时间 T_1(n) 并且 Algo2 需要时间 T_2(n)。

假设 T_1(n) 在 O(n^2) 中完成，T_2(n) 在 O(n^3) 中完成。这是否意味着存在 n0 使得对于 n > n0*，Algo1 在大小为 n 的输入上运行速度比 Algo2 快？

抱歉，我对这个问题还很陌生，我什至不确定如何开始解决这个问题。对正确方向的任何提示将不胜感激！谢谢！

Answer 1

作为反例，这里有两个计算JavaScript中整数平方的算法。

算法1：

console.log( Algorithm1( 5 ) ); // 25

function Algorithm1 ( n ) {
  let count = 0;
  for ( let i = 0; i < n; i++ )
    for ( let j = 0; j < n; j++ )
      count++;
  return count;
}

算法2：

console.log( Algorithm2( 5 ) ); // 25

function Algorithm2 ( n ) {
  return n*n;
}

算法 1 在 Ө(n²) 中，因此不在 O(1) 中。

Algorithm2 在 O(1) 中，因此通常也在 O(n³).

中

因此不存在 n0 使得 n > n0 算法 1 比算法 2 快。

与 O-notation 的算法比较

Algorithm Comparison with O-notation

algorithm

runtime

time-complexity