Question

已知算法 A 的运行时间函数为 T(n)=8T(n 2)+n2 ，其中 n 表示问题的规模，则该算法的时间复杂度为（）

A.θ（n）
B.θ（nlgn）
C.θ（n2）
D.θ（n3）

Answer 1

【答案】：D
本题需要用到特定形式的递归式分析法：
在本题中，a=8,b=2，故符合（1）的情况。时间复杂度为：O（n3）。a=16,b=4