已知算法A的运行时间函数为T(n)=8T(n／2)+n
2
，其中n表示问题的规模，则该算法的时间复杂度为_________(62)。另已知算法B的运行时间函数为T(n)=XT(n／4)+n
2
，其中n表示问题的规模。对充分大的n，若要算法B比算法A快，则X的最大值为__________(63)。
单选题
(62)
单选题
(63)
【正确答案】
C
【答案解析】解析：本题考查算法分析的基础知识。 根据主方法，先计算算法A的时间复杂度，a=8，b=2，log
b
a=log
2
8=3，而f(n)=n
2
，因此时间复杂度为Θ(n
3
)。然后计算算法B的时间复杂度，a=X,b=4，log
b
a=log
4
X，而f(n)=n
2
，若算法B和算法A的效率一样，则X应该为64(log
4
64=3)，而现在要使得B比A快，则X应该比64小，因此最大的整数应该为63。