嵌套循环的时间复杂度（Big O）计算方法

Question

我在计算以下代码的大O时遇到了问题。我并不是最聪明的人。 能否有人友好地解释一下。我的猜测是由于嵌套循环，所以它是O(N^2)，但我知道其中还有更多内容。

static inline int f1 (int a, int b)
{
 for (int c = 0; c < b; c++)
 {
   a -= n;
 }
 return a;
}

int f2 (int n) 
{
  int r = n * n * n;
  for (double i = n; i >= 0; i -= 2)
  {
     r = f1(r, i);
  }
  return r;
}

- nixgadget

---

O((N/2)^2)不是一个有效的概念。在计算O时，可以移除/合并常数。 - OmnipotentEntity

我认为这没有比这更多的了。计算大O符号相当直观，我认为。 - john

Answer 1

首先，注意到f1的运行时间完全取决于第二个参数，该参数控制循环迭代次数。因此，它的运行时间在第二个参数中是线性的。

接下来，注意到f2中的循环运行n/2次，i的值为0、2、4、6、...、n。由于i是f1的第二个参数，所以运行时间由如下公式给出：

0 + 2 + 4 + ... + n

= 2(0 + 1 + 2 + .. + n)

= 2Θ(n^2)

= Θ(n^2)

因此运行时间是Θ(n^2)。请注意，几乎所有其他内容都是旨在误导您的干扰因素。只关注控制迭代和循环的变量可以揭示您需要关注的实际逻辑。

希望这能帮助您！

- templatetypedef

---

+1，第二到第三行是通过意识到1+2+3+...+n是"小高斯"（这是英语中的叫法吗？）来完成的，这归结为1+2+3+..+n与n*(n+1)/2相同，其比例尺度为n^2。 - Frerich Raabe

Answer 2

请尽量避免使用不精确的浮点/double作为for循环计数器，可使用size_t或其他int类型。此外，从您的代码中我可以看出，您将i从double转换为int，因此不需要使用double。您的循环可以这样写：n的立方赋值给r，然后从n开始每次减2，用int类型的c进行循环计数，直到i小于0时停止循环，在内部循环中r减去n。

外层循环：O(n/2) - 每次跳2个单位，因此操作次数为n/2

内层循环：O(n/2) - 技术上讲，它迭代到i，但由于i的最大值为n/2，而内层循环每次加1 => 复杂度相同为n/2

整体复杂度：O((n/2)^2)

更新

正如其他人建议的那样，你可以折叠常量部分（在这种情况下是“/2”），但我认为像我最初发布的那样更清晰。希望这也有所帮助。

- asalic

Answer 3

就数学而言，您可以正式按照以下方式进行：

其中，op 是在 f1() 中执行的常数时间操作次数。

我本可以为 f2() 添加 op' 或类似的参数，但那似乎不必要。

为了计算操作次数 T(10)，只需让 op = 1。

- Mohamed Ennahdi El Idrissi