设算法A的时间复杂度可用递归式表示，算法B的时间复杂度可用递归式表示，若要使得算法B渐进地快于算法A，则a的最大整数为______。

admin2018-07-25 6

问题设算法A的时间复杂度可用递归式

表示，算法B的时间复杂度可用递归式

表示，若要使得算法B渐进地快于算法A，则a的最大整数为______。

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

答案A

解析对于算法A，设a=7，b=2，f(n)=n²，则log_ba＞2，因此存在常数ε，使得f(n)=O(n^log_ba-ε)，因此T(n)=Θ(n^log_ba)=Θ(n^log₂7)。
如果要使B渐进地快于算法A，则有n^log₂7＜n^log₄a，得log₂7＜log₄a，求得a＜49，冈此a的最大整数为48。

转载请注明原文地址:https://kaotiyun.com/show/j5RZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类