2. 计算机
  3. 已知算法A的运行时间函数为T(n)=8T(n／2)+n2，其中n表示问题的规模，则该算法的时间复杂度为_________(62)。另已知算法B的运行时间函数为T(n)=XT(n／4)+n2，其中n表示问题的规模。对充分大的n，若要算法B比算法A快，则X的最

已知算法A的运行时间函数为T(n)=8T(n／2)+n2，其中n表示问题的规模，则该算法的时间复杂度为_________(62)。另已知算法B的运行时间函数为T(n)=XT(n／4)+n2，其中n表示问题的规模。对充分大的n，若要算法B比算法A快，则X的最

admin2019-07-12  61
问题 已知算法A的运行时间函数为T(n)=8T(n／2)+n2，其中n表示问题的规模，则该算法的时间复杂度为_________(62)。另已知算法B的运行时间函数为T(n)=XT(n／4)+n2，其中n表示问题的规模。对充分大的n，若要算法B比算法A快，则X的最大值为__________(63)。
(63)
选项 A、15
B、17
C、63
D、65
答案C
解析 本题考查算法分析的基础知识。
根据主方法，先计算算法A的时间复杂度，a=8，b=2，logba=log28=3，而f(n)=n2，因此时间复杂度为Θ(n3)。然后计算算法B的时间复杂度，a=X,b=4，logba=log4X，而f(n)=n2，若算法B和算法A的效率一样，则X应该为64(log464=3)，而现在要使得B比A快，则X应该比64小，因此最大的整数应该为63。
转载请注明原文地址:https://kaotiyun.com/show/46CZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)