algorithm - 从 comp 类算法时间问题，n=100 = 10 秒，O(n^2) n=500 的时间是多少

Question

一个 Θ(n^2) 的算法需要 10 秒来执行 n = 100。当 n = 500 时需要多长时间？

答案 = O(n2) 是二次方，n=100, 100^2 = 10000 = 10 秒因此，n=500, (5x100) ^2 = 250000 = 250 秒

这似乎有道理但不确定。我是对的还是接近的。谢谢

Answer 1

我相信你以“好的方式”解决了你得到的任务(这可能是老师打算做的)——这个任务试图展示复杂性如何影响输入(在这个例子中它显示了 5 倍大的输入花费 25 倍的时间)。

虽然它可以帮助理解为什么 O(n^2) 与 O(n) 比较对于测量很重要，但示例不正确。

此代码是 O(n^2)，但对于 n=500，它需要 O(1)

function ohNoHowComplexityWorks(n) {
  if (n == 500) {
    return 10;
  }
  for (i=0; i < n; i++){
    for (j=0; j<n; j++){
      // anything in constant time
    }
  }
}