嵌套循环时间复杂度求解：为何该双层循环复杂度为O(n)？

First, let's restate your code clearly to make sure we're aligned:

for i = 1 to n do
    j = i
    while j < n do
        j = 2 * j

Let’s break down the analysis step by step, starting with the inner loop behavior for each i, then summing up all iterations to get the total time complexity.

Step 1: Count Inner Loop Iterations for a Single i #

For each value of i, how many times does the inner while loop run?

The loop starts with j = i and doubles j each time until j >= n. Let’s denote t_i as the number of iterations for a given i. We need to find how many doublings it takes to go from i to a value that’s at least n.

Put simply:

• First iteration: j = i (counts if i < n)
• Second iteration: j = 2i (counts if 2i < n)
• ...
• t_i-th iteration: j = i * 2^{t_i -1} (counts if this value is still less than n)
• Next step: j = i * 2^{t_i} which is >= n, so the loop stops.

Solving for t_i, we find it’s roughly equal to log2(n/i) (the "+1" from rounding up to an integer doesn’t affect our asymptotic analysis).

Step 2: Sum Iterations Across All i #

To find the total number of iterations, we need to calculate S = sum_{i=1 to n} t_i. Instead of calculating each term individually, let’s group values of i by how many times their inner loop runs:

• Group 1 (t_i=1): i values where i*2 >=n (so i > n/2). There are ~n/2 such values.
• Group 2 (t_i=2): i values where i*2 <n but i*4 >=n (so n/4 <i <=n/2). There are ~n/4 such values.
• Group 3 (t_i=3): i values where i*4 <n but i*8 >=n (so n/8 <i <=n/4). There are ~n/8 such values.
• ...
• Group k (t_i=k): i ranges from n/2^k to n/2^{k-1}, with ~n/2^k values.

This pattern continues until n/2^k >=1 (so k goes up to log2(n)).

Now the total sum S becomes:
S = 1*(n/2) + 2*(n/4) + 3*(n/8) + ... + k*(n/2^k) + ...

Factor out n:
S = n*(1/2 + 2/4 + 3/8 + 4/16 + ...)

Step 3: Evaluate the Series #

The sum inside the parentheses is a well-known infinite series:
sum_{k=1}^∞ k*(1/2^k) = 2

You can confirm this using the formula for the sum of k*x^k (valid for |x|<1): sum_{k=1}^∞ k*x^k = x/(1-x)^2. Plugging in x=1/2:
(1/2)/(1-1/2)^2 = (1/2)/(1/4) = 2

Even though our sum stops at k=log2(n), it’s still bounded by this infinite sum. So S <= n*2 = 2n.

This means the total number of iterations is at most 2n, which is O(n).

Why This Makes Sense #

Even though smaller i values (like i=1) run the inner loop ~log2(n) times, there are very few such is. As i grows, the inner loop runs fewer times, but there are far more is in those groups. The combination of these two factors balances out to a linear total number of iterations.

内容的提问来源于stack exchange，提问作者mymemesarespiciest