试题出自试卷《2025年上半年软件设计师考试综合知识真题【学员回忆版】》

问题1选项
A.⊙（nlgn）
B.⊙（n ³ ）
C.⊙（n ² ）
D.⊙（n ² lgn）

C

递归式 T(n) = 4T(n/2) + nlgn 的时间复杂度可通过 主定理 分析：
1. 主定理形式：对形如 T(n) = aT(n/b) + f(n) 的递归式，主定理通过比较 f(n) 与 n^(log_b a) 的阶来确定时间复杂度。
2. 参数分析：
a = 4，b = 2 → log_b a = log₂4 = 2，因此 n^(log_b a) = n²。
f(n) = nlgn，需与 n² 比较阶。
3. 主定理情况判断：若 f(n) = O(n^{log_b a - ε})（存在 ε > 0），则 T(n) = Θ(n^{log_b a})。这里 nlgn 的阶低于 n²（因为 lgn 的增长速度远慢于 n），且存在 ε = 0.5 使得 nlgn = O(n^{2 - 0.5}) = O(n^{1.5})。因此满足 情况1，时间复杂度为 Θ(n²)。