NOIP 提高 2016 第一轮 第 14 题：假设某算法的计算时间表示为递推关系式

题目

假设某算法的计算时间表示为递推关系式

$T(n) = 2T(\dfrac{n}{4})+\sqrt n$

$T(1) = 1$

则算法的时间复杂度为（  ）。

选项

• A. $O(n)$
• B. $O(\sqrt{n})$
• C. $O(\sqrt{n}\log{n})$
• D. $O(n^2)$

答案

C

题解

考点定位

本题考「递归式主定理」,对应大纲 4.1.1（难度【4】）。

解题过程

T(n)=2T(n/4)+√n：递归树每层工作量 2^k·√(n/4^k) = √n 恒定，共 log₄n 层：

$$T(n)=\Theta(\sqrt n\log n)$$

选 C。

易错提醒

① 主定理：a=2, b=4, f(n)=n^{1/2} 与 n^{log_b a}=n^{1/2} 同阶 ⇒ 第二情形；② 每层工作量 = a^k·f(n/b^k) 化简。