我如何找到这个三重循环的时间复杂度（大O）？

Question

for (int i = 0; i < n^2; i++) {
  for (int j = 1; j < i; j = 2j) {
    for (int k = 0; k < j; k++) {
      System.out.println("x");
    }
  }
}

我的想法是外循环是n^2，中间循环是log(n)，内循环是n，这意味着总时间复杂度是O(n^3 * log(n))，但我不确定如果这是正确的。

Answer 1

复杂度为 O(𝑛⁴):

n

的值只在

n^2

中使用，所以我们来定义

m=n^2

外循环的前两次迭代不执行任何操作（j 循环条件立即为假），因此我们可以从 2 而不是 0 开始。

打印语句是一个 O(1) 操作，因此内循环是 O(𝑗)。

我们可以这样写代码：

for (int i = 2; i < m; i++) {
  for (int j = 1; j < i; j = 2j) {
    O(j)
  }
}

现在让我们将定义

p

的 j 循环重写为

log(j)

（这里所有对数的底数都是 2）：

for (int i = 2; i < m; i++) {
  int q = ceil(log(i))
  for (int p = 0; p < q; p++) {
    O(2^p)
  }
}

内循环的复杂度代表一个几何和，因此它有一个封闭的公式，我们可以重写：

for (int i = 2; i < m; i++) {
  int q = ceil(log(i))
  O(2^q)
}

对于某些不同的

q

值，循环体将重复使用相同的

i

值，直到

i

超过 2 的下一个幂。我们可以引入一个等于

q

的变量

ceil(log(i))

，这使其自己的迭代：

for (int q = 1; q <= ceil(log(m)); q++) {          
  for (int i = 2^(q-1) + 1; i <= 2^q && i < m; i++) {
    O(2^q)
  }
}

由于

i

的值对于内部循环不再重要，我们可以使用它的迭代次数作为大 Oh 表达式的系数：

for (int q = 1; q <= ceil(log(m)); q++) {
  O(2^(q-1) * 2^q)
}

公平地说，当外循环处于最后一次迭代时，条件

i < m

会限制前一个内循环的迭代次数，但渐近地这并不重要。

我们可以简化：

for (int q = 1; q <= ceil(log(m)); q++) {
  O(4^q)
}

这又是一个几何序列，总结为：

O(4^log(𝑚))

= O([2^log(𝑚)]²)

= O(𝑚²)

= O(𝑛⁴)