关于O(n)与O(nlogn)时间复杂度的困惑求解

Great question—let’s break this down step by step to clear up your confusion!

First, let’s restate the original code for clarity:

x = n 
while ( x > 0 ) { 
    y = x 
    while ( y > 0 ) { 
        y = y - 1 
    } 
    x = x / 2 
}

Why the original code is O(n), not O(nlogn) #

Your intuition about the outer loop being logarithmic is correct—it runs roughly log₂(n) times (since we divide x by 2 each iteration until it hits 0). But the inner loop’s run time decreases each time the outer loop runs, which changes the total count.

Let’s calculate the total number of inner loop iterations:

• First outer iteration: inner loop runs n times
• Second outer iteration: inner loop runs n/2 times
• Third outer iteration: inner loop runs n/4 times
• ...
• Last outer iteration: inner loop runs 1 time

This is a geometric series: n + n/2 + n/4 + ... + 1. The sum of this series is 2n - 1 (a standard result for geometric series with ratio 1/2). When we drop constants and lower-order terms, this simplifies to O(n). The key here is that the inner loop’s work shrinks exponentially, so the total isn’t just "logarithmic outer * linear inner"—it’s a sum that collapses to a linear total.

What happens if we set y = n instead of y = x? #

If we modify the code to initialize y = n every time, the inner loop runs exactly n iterations every time the outer loop runs.

Since the outer loop still runs log₂(n) times, the total number of inner loop iterations becomes n * log₂(n). Dropping constants, this gives us O(nlogn). Here, the inner loop’s work doesn’t decrease—each outer iteration does the same fixed amount of linear work, so multiplying by the logarithmic number of outer iterations gives the combined nlogn complexity.

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