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

admin2010-12-17 45

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

选项 A、O(n)
B、

C、O(n²)
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

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