嵌套 for 循环的时间复杂度

Question

给定以下嵌套 for 循环：

for (int i=n; i>1; i=i/2):
    for (int j=i; j<n; j=j*2)
        # O(1) expression

整个循环的时间复杂度是多少？我的答案是 O(log(n)*log(n)) 但我不确定它是否正确。

Answer 1

这是使用格言的好地方

When in doubt, work inside out!

也就是说，首先采用最内层的循环并将其替换为表示它正在执行多少工作的表达式，然后重复此操作直到完成。

在你的例子中，最里面的循环是

for (int j=i; j<n; j=j*2)
    # O(1) expression

现在，这做了多少工作？为了回答这个问题，让我们考虑一下循环是如何工作的。在每次迭代中，j 的值都会比之前翻倍。由于 j 从 i 开始，j 取的值将是 i、2i、4i、8i 等，更一般地，在循环的第 k 次迭代中，j 的值将是 2^k·我。一旦这个值等于或超过 n，循环就会终止，这发生在

2^k · i = n

2^k = n / i

k = lg(n / i)

所以这意味着我们要运行循环进行 Θ(log (n / i)) 次迭代。如果我们将其代入原始循环，我们将得到以下代码：

for (int i=n; i>1; i=i/2):
    Do Θ(log (n / i)) work;

那么最终需要完成多少工作？好吧，外循环将运行一次 i = n，然后一次 i = n/2，然后一次 i = n/4，等等，所以完成的总工作是

Θ(log (n/n) + log(n/(n/2)) + log(n/(n/4)) + ... + log(n / 1))

= Θ(log 1 + log 2 + log 4 + log 8 + ... + log n)

= Θ(log 2⁰ + log 2¹ + log 2² + log 2³ + ... + log 2^{log n})

Θ(0 + 1 + 2 + ... + log n)

记住 0 + 1 + 2 + ... + k = k(k + 1) / 2 = Θ(k²)，所以这里完成的总功是

Θ(0 + 1 + 2 + ... + log n)

= Θ(log² n).

得出这个答案的关键技术是从内部开始，将对数与重复将某物的大小加倍时执行的循环迭代次数以及 1 + 2 + ... + k 的公式联系起来。

嵌套 for 循环的时间复杂度

Time complexity for a nested for loop

algorithm

big-o

time-complexity