如何不使用主定理分析区间求和递归函数的时间复杂度？

Great question! Let's walk through how to analyze the time complexity of this recursive sum function without leaning on the Master Theorem—we'll use plain, intuitive approaches that let you see exactly where the complexity comes from.

First, let's restate your function for reference:

def sum_func(a, b):
    if a == b:
        return a
    mid = (a+b) // 2
    return sum_func(a, mid) + sum_func(mid+1, b)

Intuitive Breakdown of the Recursion #

This function works by splitting the interval [a, b] into two halves repeatedly until each sub-interval has exactly one number (the base case). Then it adds all those single numbers back together. It's almost identical to the "split phase" of merge sort—except here, the "merge" step is just a simple addition (which takes constant time).

Step-by-Step Complexity Derivation #

We'll use two complementary approaches to confirm the time complexity: expanding the recursion formula, and counting total function calls.

Approach 1: Expand the Recursive Formula #

Let's define T(n) as the time needed to compute the sum of n numbers (where n = b - a + 1).

• Base case: When n=1 (a == b), we just return the number—this takes constant time, so T(1) = O(1).
• Recursive case: When n>1, we do three constant-time operations (calculate mid, add two results) plus two recursive calls to subproblems of size n/2. So:

  T(n) = 2*T(n/2) + O(1)
  

Now let's expand this step by step:

1. 1st level: T(n) = 2*T(n/2) + C (C is a constant for all O(1) operations)
2. 2nd level: Substitute T(n/2) → T(n) = 2*(2*T(n/4) + C) + C = 4*T(n/4) + 2C + C
3. 3rd level: Substitute T(n/4) → T(n) = 4*(2*T(n/8) + C) + 2C + C = 8*T(n/8) + 4C + 2C + C
4. ...
5. k-th level: When n/(2^k) = 1 (we hit the base case), k = log2(n). Now:

   T(n) = 2^k*T(1) + C*(1 + 2 + 4 + ... + 2^(k-1))
   

Calculate each part:

• 2^k = n, so the first term is n*O(1) = O(n)
• The second term is a geometric series: 1 + 2 + 4 + ... + 2^(k-1) = 2^k - 1 = n - 1, so this becomes C*(n-1) = O(n)

Adding both parts gives T(n) = O(n) + O(n) = O(n).

Approach 2: Count Total Function Calls #

This is even more straightforward:

• Base case calls: Every number from a to b will trigger exactly one base case call (when we split down to that single number). That's n calls total.
• Non-base case calls: To split n numbers into n single elements, we need n-1 split operations (each split turns one interval into two). Each split is one non-base call.

Total calls: n + (n-1) = 2n-1, each taking constant time. So overall time is O(n).

General Strategy for Recursive Complexity (No Master Theorem) #

When you want to avoid the Master Theorem, these methods work for most divide-and-conquer problems:

• Recursion tree expansion: Draw out each level of recursive calls, calculate the time cost per level, then sum all levels.
• Count calls/operations: Track how many times each type of operation (base case, split, merge) happens, then multiply by their individual time costs.
• Mathematical induction: Assume the complexity holds for subproblems of size n/2, then prove it holds for size n, and verify the base case.

All these methods boil down to unpacking the recursion's actual behavior instead of relying on a formula—you'll build a better intuition for how recursion affects performance this way.

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