与 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;
}

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

算法 2 在 O(1) 中，因此在 O(n³) 中也是平凡的。

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