递归方法时间复杂度求解：多分支及记忆化递归分析

Hey there! Let's break down your questions step by step—this is a great chance to dig into recursive time complexity analysis, especially with and without memoization.

1. Time Complexity of the Final Line (Original Recursion) #

First, let's clarify: the final line's direct overhead (arithmetic operations like +, *, and 4*n) is O(1)—these are all constant-time operations for a single integer n. But the real cost here comes from the three recursive calls:

• F(n-3): one call to the function with input n-3
• 5*F(n-4): the coefficient 5 is just a constant multiplier (it doesn't affect the number of recursive calls), so this is equivalent to one call to F(n-4)
• 10*F(n/5): similarly, the 10 is irrelevant for call count—this is one call to F(n/5)

So the final line's total time isn't standalone; it's the sum of the time taken by those three recursive calls plus O(1) constant time.

2. Overall Time Complexity of the Original Recursive Function #

Let's formalize the time complexity with a recurrence relation. Let T(n) represent the time to compute F(n).

Recurrence Relation: #

• Base case: When n ≤ 1, T(n) = O(1) (constant time for the return statement)
• For n > 1:

  T(n) = T(n-3) + T(n-4) + T(n/5) + O(n)
  

  (The O(n) comes from the 4*n term plus constant arithmetic operations; coefficients like 5 and 10 are dropped because they don't affect asymptotic complexity.)

Analysis: #

To find the asymptotic behavior, we look at which term dominates:

1. Linear recursive terms (T(n-3) + T(n-4)): This is a linear recurrence relation similar to Fibonacci, but with a longer lag. Its characteristic equation is r⁴ = r + 1, whose largest positive real root is approximately 1.22. This means these terms grow exponentially: O(rⁿ) where r ≈ 1.22.
2. Divisive term (T(n/5)): This term grows as O(r^(n/5)) = O((r^(1/5))ⁿ), and r^(1/5) ≈ 1.04—far slower than the exponential growth of the linear terms.
3. Linear term (O(n)): Linear growth is negligible compared to exponential growth.

So the dominant term is the exponential growth from T(n-3) + T(n-4). The overall time complexity of the original recursive function is O(rⁿ) (exponential time), where r ≈ 1.22 is the largest root of r⁴ = r + 1.

3. Time Complexity with Memoization #

Memoization changes everything by storing computed values in the values array, so each n is calculated exactly once. Now we just need to count how many unique n values are ever accessed, and multiply by the time per calculation.

Counting Unique n Values: #

• Linear branches: Starting from n, we have sequences like n, n-3, n-6, ... and n, n-4, n-7, ... until we hit ≤1. Each of these has O(n) terms (since we subtract 3/4 each step).
• Divisive branches: We also have sequences like n, n/5, n/25, n/125, ... until ≤1—this is O(log₅ n) = O(log n) terms. Each of these divisive values will spawn its own linear branches (e.g., n/5 leads to n/5 -3, n/5 -6, ...), but the total number of these is:

  O(n/5 + n/25 + n/125 + ...) = O(n * (1/5 + 1/25 + 1/125 + ...)) = O(n)
  

  (This is a geometric series that converges to a constant factor of n.)

Adding these together, the total number of unique n values is O(n).

Time per Calculation: #

Each time we compute F(n) (once per unique n), we do constant-time operations: checking the memo array, computing the arithmetic (all memoized calls are O(1) lookups), and storing the result.

So the overall time complexity with memoization is O(n).

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