2. 计算机
  3. 某算法的时间代价递推关系为T(n)=2T(n/2)+n，T(1)=1，则该算法的时间复杂度为______。

某算法的时间代价递推关系为T(n)=2T(n/2)+n，T(1)=1，则该算法的时间复杂度为______。

admin2010-12-17  41
问题 某算法的时间代价递推关系为T(n)=2T(n/2)+n，T(1)=1，则该算法的时间复杂度为______。
选项 A、O(n)
B、
C、O(n2)
D、O(1)
答案B
解析 由时间代价严格推出时间复杂度比较复杂，对于这种题，可用特例验证，不过需要注意的是特例不能取太少，至少n取到5，这样规律基本就可以确定了。
   T(1)=1
   T(2)=2T(1)+2=4
   T(3)=2T(1)+3=5
   T(4)=2T(2)+4=12
   T(5)=2T(2)+5=13
   很容易排除D选项，其递增速率介于O(n)和O(nsup>2)之间，故选B。
转载请注明原文地址:https://kaotiyun.com/show/74xZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

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

软考中级

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