algorithm - 与 O 表示法的算法比较

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 的运行速度比 Algo2 快n？

抱歉，我对这个主题很陌生，我不知道如何开始解决这个问题。任何朝着正确方向的提示将不胜感激！谢谢！

标签： algorithmruntimetime-complexity

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).

算法 2 在 中O(1)，因此也很简单O(n³)。

因此n0，对于算法 1，不存在n > n0比算法 2 更快的情况。