求解线性时间选择算法最坏情况渐近时间复杂度的技术咨询

Hey there! I totally get where you're coming from—linear time selection's recurrence relation is a perfect example of when the Master Method (which only handles single-term recursions like aT(n/b) + f(n)) can't help. Let's walk through the two most reliable methods to find its worst-case asymptotic runtime.

First, let's align on the standard worst-case recurrence for linear time selection (the version that splits elements into groups of 5, finds medians, and recurses):

T(n) = T(7n/10) + T(n/5) + cn

where c is a positive constant representing the linear-time work done outside the recursive calls.

1. Substitution Method (Induction-Based) #

This is the most rigorous approach—we guess an asymptotic bound and prove it holds with mathematical induction.

Step 1: Guess the bound #

We suspect the worst-case runtime is linear, so let's formalize that guess: T(n) = O(n). This means there exists some constant d > 0 and threshold n₀ such that for all n ≥ n₀, T(n) ≤ dn.

Step 2: Inductive proof #

• Base case: For small n (e.g., n ≤ n₀), T(n) is a constant. We can choose d large enough to satisfy T(n) ≤ dn for all these small values.
• Inductive step: Assume the bound holds for all k < n (i.e., T(k) ≤ dk for all k < n). Substitute this into the recurrence:

  T(n) ≤ d*(7n/10) + d*(n/5) + cn
  = d*(7n/10 + 2n/10) + cn
  = d*(9n/10) + cn
  = n*(9d/10 + c)
  

  We want this to be ≤ dn, so solve for d:

  9d/10 + c ≤ d → c ≤ d/10 → d ≥ 10c
  

  If we pick d = 10c, the inequality holds. Thus, our guess is valid, so T(n) = O(n).

To confirm the bound is tight (i.e., Θ(n)), repeat the process for the lower bound: guess T(n) ≥ dn, and show it holds with a similar inductive step (the positive linear term cn makes this straightforward).

2. Recursion Tree Method #

This method is more visual and helps you intuitively see how costs accumulate across recursive levels:

• Level 0: The root node represents T(n), with non-recursive cost cn.
• Level 1: Splits into two nodes: T(7n/10) and T(n/5). Combined non-recursive cost here is c*(7n/10 + n/5) = c*(9n/10).
• Level 2: Each of those nodes splits again. Combined non-recursive cost becomes c*((7/10)²n + 2*(7/10)(1/5)n + (1/5)²n) = c*(9/10)²n.
• General Level k: Combined non-recursive cost is c*(9/10)ᵏn.

Sum the costs across all levels:

Total cost = cn + c*(9/10)n + c*(9/10)²n + ...

This is an infinite geometric series with first term cn and common ratio 9/10 (which is less than 1). The sum simplifies to:

cn * (1 / (1 - 9/10)) = 10cn

Since this sum is a constant multiple of n, the total runtime is O(n).

Key Takeaway #

The Master Method excels at single-branch recursions, but when you have multiple recursive terms (like in linear time selection), substitution or recursion tree methods are your go-to tools. Both confirm that the worst-case asymptotic runtime is Θ(n).

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