嵌套回路的时间复杂性 - 始终只是它们每个分开的乘法吗？

Question

例如，在查看此代码时：

for (int i = 1; i < n; i*=2)
  for (int j = 0; j < i; j +=2)
  {
    // some contstant time operations
  }

这么简单说，因为外循环是日志，并且内部循环是n，因此结果结合了NLOGN的大（O）？

Answer 1

这是问题中对示例的分析。为简单起见，我将忽略内部循环中2的增量，并将其视为1，因为就复杂性而言，它无关紧要 - 内部循环在i和2的常数因子无关紧要。
因此，我们可以注意到，外循环正在产生i值，这是2由n封顶的功能，也就是说：

1, 2, 4, 8, ... , 2^(log2 n)

这些数字这也是内部循环中每个i的“恒定时间操作” “恒定时间操作”的数字。
因此，我们要做的就是总结上述系列。很容易看出这些是几何系列：

2^0 + 2^1 + 2^2 + ... + 2^(log2 n)

它具有众所周知的解决方案：

（来自 wiki ）

我们有a = 1 a = 1，r = 2和...良好n_from_the_image = log n。在这里，我们对不同变量有相同的名称，因此这是一个问题。

现在，让我们替换并获得该总和

(1-2^((log2 n) + 1) / (1 - 2) = (1 - 2*n) / (1-2) = 2n-1

是线性o（n）复杂性。

Answer 2

通常，我们将o时间复杂性作为执行最终循环的次数（在这里我们假设最内在的循环由o的语句组成（（ 1）时间复杂性）。

---

考虑您的榜样。第一个循环执行o（log n）次，第二个最内向的循环执行o（n）次。如果某物o（n）正在执行o（log n）次，那么是的，最终的时间复杂性只是它们乘以：o（n log n og n log n ）。

通常，这与大多数嵌套的循环有关：您可以假设它们的大时段复杂性是每个循环的时间复杂性，乘以乘。

---

但是，当您可以考虑Break语句时，此规则有例外。如果循环有可能提早爆发，那么时间的复杂性将有所不同。

看看这个示例我刚刚想到：

for(int i = 1; i <= n; ++i) {
    int x = i;
    while(true) {
        x = x/2;
        if(x == 0) break;
    }
}

嗯，最内向的循环是o（infinity），所以我们可以说总的时间复杂性是o（n） * o（ Infinity）= O（Infinity）？否。在这种情况下，我们知道最内向的循环将始终突破o（log n），给出了总o（n log n）时间复杂性。