设算法A的时间复杂度可用递归式表示,算法B的时间复杂度可用递归式表示,若要使得算

练习题库2022-08-02  31

问题 设算法A的时间复杂度可用递归式表示,算法B的时间复杂度可用递归式表示,若要使得算法B渐进地快于算法A,则a的最大整数为(  )。A.48B.49C.13D.14

选项 A.48
B.49
C.13
D.14

答案 A

解析 题目要求使得算法B渐进地快于算法A,即B的时间复杂度小于A的时间复杂度。
对算法A进行简单的化简,令n=n/2,我们可以得到算法A的T(n)=49T(n/4)+11/4n2;
而算法B的T(n)=aT(n/4)+n2,而根据渐进的规则,算法A的时间复杂度应该为49T(n/4),而算法B的时间复杂度应该为aT(n/4),因此a的取值应该要小于49,本题只有A选项符合。
转载请注明原文地址:https://tihaiku.com/congyezige/2409980.html

最新回复(0)