求助：求解两段嵌套循环代码的Big O表示法（时间复杂度）

Hey there! Let's break down these two code snippets to nail down their Big O time complexity—you had a solid start with the first one, but let's clarify the details, then work through the confusing second one.

First, let's look at the code you shared:

int sum = 0;
for (int k = n; k > 0; k /= 2 )
    for (int i = 0; i < k; i++)
        sum++;

You initially thought this was O(n log n), but let's calculate the total number of times sum++ executes to get the right answer.

The outer loop runs log₂(n) times (since we start at n and divide by 2 each time until we hit 0). But the inner loop doesn't run n times every iteration—it runs a decreasing number of times: first n times, then n/2, then n/4, all the way down to 1.

Adding those iterations gives us a geometric series:

n + n/2 + n/4 + ... + 1 = 2n - 1

In Big O notation, we drop constants and lower-order terms, so this simplifies to O(n). Your call on the outer loop's iteration count was spot-on, but the total inner loop operations don't multiply by log n—they add up to a linear amount instead.

Now let's tackle the second snippet that gave you trouble:

int sum = 0;
for (int i = 1; i < n; i *= 2 )
    for (int j = 0; j < i; j++)
        sum++;

Again, the outer loop runs log₂(n) times (starting at 1, multiplying by 2 each time until we reach or exceed n). The inner loop runs i times per outer iteration, where i grows exponentially: 1, 2, 4, 8, ..., up to the largest power of 2 less than n.

Let's sum those iterations too—this is another geometric series, just increasing instead of decreasing:

1 + 2 + 4 + ... + (n/2) = n - 1

Dropping constants, this also simplifies to O(n). The key insight here is that even though the inner loop gets longer each time, the total number of operations still adds up to a linear amount relative to n, not a logarithmic multiple.

To wrap up: both snippets end up doing roughly 2n operations in total, so their growth order is linear, not linearithmic.

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