某算法的时间代价递推关系为T(n)=2T(n／2)＋n,T(1)=1,则该算法的时间复杂度为______。A.O(n)B.C.O(n

Question

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

A．O(n)

B．

C．O(n2)

D．O(1)

Answer 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。