大 O 表示法 - 增长率

Question

我正在尝试了解我的推理是否正确：

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

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

我想说 O(n)，因为我们正在处理一个 for 循环和 sum++，它被迭代说 n 次，但后来看到这个我意识到我们根本没有处理 n，因为我们得到了数量这个for循环迭代的次数......但在我看来，说它有一个O（1）的大O是错误的，因为增长是线性的而不是恒定的并且取决于这个循环的大小（虽然循环是 'constant'）。我说这是 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) 因为：

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

Answer 2

第一个要么是 O(1)，要么就是一个错误的问题，就像你理解的那样。

第二个是O(n⁶)。试着想象一下内循环的大小。在第一次迭代中，它将是 1。在第二次迭代中，它将是 2。在第 i 次，它将是 i，在最后一次，它将是 n*n*n。所以它将是 n*n*n/2，但那是 O(n*n*n)。也就是说，乘以外部 O(n³) 是 O(n⁶ ) 整体。

Answer 3

虽然其他人针对您的问题计算的 O() 可能是正确的，但这里有更多的见解应该有助于描绘整个渐近分析故事的概念前景。

I think what is throwing me is where 'n' is not appearing and we're given a constant or another variable and all of a sudden I'm assuming n must not be considered for that section of code.

理解这一点的最简单方法是确定一行代码的执行是否受到 by/related n 的当前值的影响。如果内部循环是，比方说，j < 10 而不是 j < i，那么复杂度很可能是 O(n^3).

为什么 any 常数被认为是 O(1)？

起初这听起来可能有点违反直觉，但是，这里有一个小的概念性总结来澄清一下。假设您的第一个循环运行s 1000 次。然后你将它设置为 10^1000 次并试着相信嘿，它不再需要相同的时间了。很公平！即使现在您的计算机可能需要多花 5 秒才能运行同一段代码，时间复杂度仍然保持为 O(1)。这实际上意味着您可以实际计算计算机执行该段代码所花费的时间，并且它将永远保持不变（对于相同的配置）。

Big-Oh 实际上是 输入上的函数而不是离散值本身的度量（time/space ).

我希望以上解释也有助于阐明为什么我们实际上忽略了 O() 表示法中的常量。

为什么这个 Big-Oh 的东西如此普遍，为什么首先使用它？

我想包括这个额外的信息，因为我自己在第一次学习这个主题时就想到了这个问题。渐近时间复杂度是对任何算法的先验分析，以了解该程序的最坏（Big-Oh）行为（time/space），而不管输入的大小。例如。您的第二个代码的性能不会比 O(n^6) 差。泛化是因为从一台计算机到另一台计算机，只有不断变化，而不是大哦。

随着经验的增加，您会发现实际上您希望算法的时间复杂度尽可能地小。直到多项式函数它都很好。但是对于大输入，如果您尝试运行具有 O(k^n) 或 O(n^n) 阶指数时间复杂度的算法，那么今天的计算机就会开始咳嗽，例如。旅行商和其他 NP-C/H 问题。

希望这会增加信息。 :)

大 O 表示法 - 增长率

Big O Notation - Growth Rate

algorithm

big-o