使用主方法求解递归方程 T(n) = 3T(n/4) + nlogn

使用主方法求解递归方程 T(n) = 3T(n/4) + nlogn：

1. 将递归方程表示成通用形式：T(n) = aT(n/b) + f(n)，其中 a = 3，b = 4，f(n) = nlogn。

2. 求出 b 的对数：log4(3) ≈ 0.793。

3. 比较 f(n) 与 nlogba 的大小关系：

• 当 f(n) ∈ O(nlogba-ε)（其中 ε > 0），即 nlogn ∈ O(nlog4(3)-ε) 时，解是 T(n) ∈ Θ(nlog4(3)))。

• 当 f(n) ∈ Θ(nlogba)（即 nlogn ∈ Θ(nlog4(3))）时，解是 T(n) ∈ Θ(nlogba log n)。

• 当 f(n) ∈ 𝛀(nlogba+ε)（其中 ε > 0），即 nlogn ∈ 𝛀(nlog4(3)+ε) 时，解是 T(n) ∈ Θ(f(n)))。

4. 因为 nlogn ∈ Θ(nlog4(3))，所以解是 T(n) ∈ Θ(nlogba log n)。