递归函数recursion的大O、大Θ、大Ω时间复杂度求解及解释

Let's break down the time complexity of this recursive function step by step — I get why this feels confusing at first, recursive relations can be tricky to wrap your head around, but we'll unpack it together.

First, here's the function we're analyzing:

void recursion(int n) { 
    int i; 
    if (n == 0) { 
        return; 
    } 
    for (i = 0; i < n; i++) { 
        recursion(i); 
    } 
}

Step 1: Define the time complexity function #

Let’s call T(n) the total number of operations performed by recursion(n). This helps us formalize the recursive behavior into a mathematical relation.

• When n = 0, the function immediately returns with no extra work. This is a constant number of operations, so we write T(0) = c where c is a fixed constant.
• When n > 0, the function runs a loop with n iterations (from i=0 to i=n-1). Each iteration calls recursion(i), plus the loop itself has small constant overhead (initializing i, checking the loop condition, incrementing i). This gives us the recurrence relation:

  T(n) = T(0) + T(1) + T(2) + ... + T(n-1) + d*n
  

  Here, d is another constant representing the loop's per-iteration overhead.

Step 2: Spot the pattern with small values #

Calculating T(n) for small n makes the exponential growth obvious:

• T(0) = c
• T(1) = T(0) + d*1 = c + d
• T(2) = T(0) + T(1) + d*2 = c + (c+d) + 2d = 2c + 3d
• T(3) = T(0) + T(1) + T(2) + d*3 = c + (c+d) + (2c+3d) + 3d = 4c + 7d
• T(4) = T(0)+T(1)+T(2)+T(3)+d*4 = c + (c+d) + (2c+3d) + (4c+7d) +4d = 8c +15d

Look at the coefficients:

• The coefficient of c is 2^(n-1) (e.g., n=3 uses 4=2^2, n=4 uses 8=2^3)
• The coefficient of d is 2^n - 1 (e.g., n=3 uses 7=2^3-1, n=4 uses 15=2^4-1)

We can rewrite T(n) as:

T(n) = c*2^(n-1) + d*(2^n - 1)

Simplifying this, the dominant term is 2^n — all other terms are constants or scaled by 2^n, so the function grows exponentially with base 2.

Step 3: Formalize with induction (for rigor) #

To confirm this holds for all n, we use mathematical induction:

Prove T(n) = O(2^n)

Assume for all k < n, T(k) ≤ K*2^k (where K is a constant). Then:

T(n) = sum_{k=0}^{n-1} T(k) + d*n ≤ K*(2^0 + 2^1 + ... + 2^{n-1}) + d*n

The sum 2^0 + ... + 2^{n-1} is a geometric series equal to 2^n - 1 (which is ≤ 2^n). For n ≥ 1, n ≤ 2^n, so:

T(n) ≤ K*2^n + d*2^n = (K + d)*2^n

This proves T(n) grows no faster than 2^n.

Prove T(n) = Ω(2^n)

We need to show T(n) grows at least as fast as 2^n. For n ≥ 2, T(n) = sum_{k=0}^{n-1} T(k) + d*n ≥ T(n-1) + T(n-2). Using our pattern, T(n-1) ≥ c*2^{n-2} and T(n-2) ≥ c*2^{n-3}, so:

T(n) ≥ c*2^{n-2} + c*2^{n-3} = c*3*2^{n-3} ≥ c*2^{n-1}

Since 2^{n-1} is a constant multiple of 2^n, this proves T(n) grows no slower than 2^n.

Combine for Θ(2^n)

Since T(n) is both O(2^n) and Ω(2^n), it's exactly Θ(2^n). That’s why all three notations (big O, big Θ, big Ω) equal 2^n here — the function’s growth rate is strictly exponential with base 2.

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