如何求解递归复杂度方程T(n)=sqrt(n)T(sqrt(n))+nlogn？附本人解法

Hey there! Let's break down how to solve the recurrence relation T(n) = sqrt(n)T(sqrt(n)) + n log n step by step. I'll use the substitution method, which is ideal for this type of recursive equation.

Step 1: Substitute Variables to Simplify the Recurrence #

First, let's make a substitution to turn the nested square roots into a linear recursion. Let n = 2^k (we can assume n is a power of 2 for asymptotic analysis—this doesn't affect the final complexity result).

With this substitution:

• sqrt(n) = 2^{k/2}
• log n = k (we'll ignore the base of the logarithm since it only affects a constant factor in asymptotic complexity)

Define a new function S(k) = T(2^k). Plugging this into the original recurrence gives us:

S(k) = 2^{k/2} * S(k/2) + 2^k * k

Step 2: Normalize the Recurrence #

Divide both sides of the equation by 2^k to simplify the terms involving S:

S(k)/2^k = S(k/2)/2^{k/2} + k

Now let R(k) = S(k)/2^k. This transforms the recurrence into a much simpler linear form:

R(k) = R(k/2) + k

Step 3: Solve the Simplified Recurrence #

We can solve R(k) = R(k/2) + k using either the expansion method or the Master Theorem. Let's cover both:

Option 1: Expansion Method

Assume k = 2^m (again, this is valid for asymptotic analysis). Expand the recurrence step by step:

R(k) = R(k/2) + k
= R(k/4) + k/2 + k
= R(k/8) + k/4 + k/2 + k
...
= R(1) + 2 + 4 + ... + k

The base case R(1) = S(1)/2^1 = T(2)/2, which is a constant (Θ(1)) since T(2) is a fixed value for small n.

The sum 2 + 4 + ... + k is a geometric series that sums to k - 1 (since k = 2^m, the sum is 2^m - 1). So:

R(k) = Θ(1) + k - 1 = Θ(k)

Option 2: Master Theorem

For the recurrence R(k) = a R(k/b) + f(k):

• a = 1 (number of subproblems)
• b = 2 (factor by which the input size shrinks)
• f(k) = k (the non-recursive cost)

We check the conditions of the Master Theorem:

• log_b a = log_2 1 = 0
• f(k) = k grows faster than k^0 (i.e., f(k) = Ω(k^{0 + ε}) for ε = 1)
• The regularity condition holds: a * f(k/b) = f(k/2) = k/2 ≤ c * f(k) for c = 1/2 < 1

By the Master Theorem (Case 3), R(k) = Θ(f(k)) = Θ(k).

Step 4: Convert Back to the Original Function #

Now we reverse our substitutions to get back to T(n):

• Since R(k) = Θ(k), we have S(k) = 2^k * R(k) = 2^k * Θ(k)
• Remember n = 2^k, so k = log n. Substituting this in gives:

T(n) = S(k) = Θ(n log n)

So the asymptotic complexity of the recurrence is Θ(n log n).

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