2. 从业资格
  3. 已知算法A的运行时间函数为T(n)=8T(n/2)+n2，其中n表示问题的规模，

已知算法A的运行时间函数为T(n)=8T(n/2)+n2，其中n表示问题的规模，

最全题库2022-08-02  58
问题 已知算法A的运行时间函数为T(n)=8T(n/2)+n2，其中n表示问题的规模，则该算法的时间复杂度为（　　）。另已知算法B的运行时间函数为T(n)=XT(n/4)+n2，其中n表示问题的规模。对充分大的n，若要算法B比算法A快，则X的最大值为（　　）。问题1选项A.Θ(n)B.Θ(nlgn)C.Θ(n2)D.Θ(n3)问题2选项A.15B.17C.63D.65
选项
答案 DC
解析 本题需要用到特定形式的递归式分析法：在本题中，a=8,b=2，故符合（1）的情况。时间复杂度为：Θ(n3)。第一空选择D选项。对于算法B的运行时间函数为T(n)=XT(n/4)+n2，同样带入分析，a=X，b=4，f(n)=n2。若要算法B与算法A一样快，即时间复杂度一致，则满足条件（1），且，此时带入算法B的变量，即log4X=3，即X=64，现在要求算法B更快，即时间复杂度更小，所以X应该小于64，可取的最大值为63。第二空选择C选项。
转载请注明原文地址:https://tihaiku.com/congyezige/2410383.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

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