Python函数def foo(n)的时间复杂度为何是O(n)？求解释

Alright, let’s break down why this function has a time complexity of O(n) — first, let’s look at the code we’re analyzing:

def foo(n):
    for i in range(n):
        for k in range(1,i):
            if k > n/k:
                return k

Let’s unpack the behavior step by step:

• The outer loop runs n times (for i from 0 to n-1), but the inner loop range(1,i) only executes when i > 1 (since range(1,1) and range(1,0) are empty sequences). We can safely ignore the first two outer loop iterations, as they do no work.
• The critical condition here is k > n/k. Rearranging this (since k is a positive integer, the inequality direction stays the same) gives us k² > n, or k > sqrt(n). As soon as k crosses this threshold, the function immediately returns and halts all execution.

Now let’s calculate the total number of iterations before the function returns (this is the worst-case scenario for valid inputs where the function does return, which applies to all n >= 3):

• For each i starting at 2, the inner loop runs i-1 times (since k ranges from 1 to i-1).
• We need the smallest i where i-1 > sqrt(n) — that’s i = floor(sqrt(n)) + 2, because k has to reach sqrt(n)+1 to trigger the return condition.
• The total number of iterations across all inner loops up to this i is the sum of integers from 1 to floor(sqrt(n)) + 1.

The sum of the first m integers is given by the formula m*(m+1)/2. Here, m is approximately sqrt(n), so substituting that in gives us:
(sqrt(n) * (sqrt(n)+1))/2 ≈ (n + sqrt(n))/2

When we drop lower-order terms (like sqrt(n)) and constant factors (the 1/2), this simplifies to O(n).

You might be thinking, "Wait, sqrt(n) is way smaller than n" — and that’s true, but the cumulative sum of the first sqrt(n) integers scales with n, not sqrt(n). For example, if n = 10000 (where sqrt(n) = 100), the total iterations would be 100*101/2 = 5050 — roughly half of n, which is clearly a linear relationship.

For edge cases where the function doesn’t return (like n = 1 or n = 2), the time complexity is O(1), which is still bounded by O(n).

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