algorithm - 大 O 表示法 - 增长率

Question

我试图了解我的推理是否正确:

如果我得到以下代码片段并要求我找出它是 Big O:

 for(int i = 3; i < 1000; i++)
    sum++;

我想说 O(n)，因为我们正在处理一个 for 循环和 sum++，它被迭代说 n 次，但后来看到这个我意识到我们根本没有处理 n，因为我们给定了次数这个for循环迭代......但在我看来，说它有O(1)的大O是错误的，因为增长是线性的而不是恒定的并且取决于这个循环的大小(虽然循环是'持续的')。我说这是 O(n) 是否正确？

此外，另一个让我思考的问题具有类似的设置:

 for(int i = 0; i < n * n * n; i++)
    for(int j = 0; j < i; j++)
       sum++;

现在我又一次知道，在处理包含外循环和内循环的嵌套循环时，我们将使用乘法规则来导出我们的大 O。假设内循环实际上是 j < n 那么我会说这段代码的大 O 是 O(n^4) 但事实并非如此，我们有第二个循环运行它的迭代 i 而不是 n 那么将它说成 O 的大订单是否正确(n^3)?

我认为让我感到困惑的是“n”没有出现的地方，我们得到了一个常量或另一个变量，突然之间我假设 n 不能被考虑用于该部分代码。然而，话虽如此，我推理的另一部分告诉我，尽管没有看到“n”，但我仍应将代码视为有 n，因为无论变量如何，增长率都是相同的？

Answer 1

如果您认为代码始终在函数内，则效果最好，函数的参数用于计算复杂度。因此:

// this is O(1), since it always takes the same time
void doSomething() {
    for(int i = 3; i < 1000; i++)
        sum++;
}

和

// this is O(n^6), since it only takes one argument
// and if you plot it, the curve matches t = k * n^6
void doSomethingElse(int n) {
  for(int i = 0; i < n * n * n; i++)
     for(int j = 0; j < i; j++)
        sum++;
}

最后，big-O 的全部意义在于说明运行时间(或内存占用；但如果您什么都不说，您指的是运行-次)看起来随着问题规模的增加。内部发生的事情并不重要(尽管您可以使用它来估计复杂性)——真正重要的是您将在外部测量什么。

仔细观察你的第二个片段，它是 O(n^6) 因为:

• 外层循环恰好运行 n^3 次；内部循环平均运行 n^3/2 次。
• 因此，内部总和运行 n^3 * k * n^3 次(k 为常数)。在大 O 表示法中，即 O(n^6)。