考研题,求时间复杂度,请说明下理由,假定问题规模为N时,某递-查字典问答网
分类选择

来自林春梅的问题

  考研题,求时间复杂度,请说明下理由,假定问题规模为N时,某递归算法的时间复杂度记为T(N),已知T(1)=1,T(N)=2T(N/2)+N/2,用O表示的时间复杂度为()AO(N)BO(NlogN)CO(N²)DO(N²logN)

  考研题,求时间复杂度,请说明下理由,

  假定问题规模为N时,某递归算法的时间复杂度记为T(N),已知T(1)=1,T(N)=2T(N/2)+N/2,用O表示的时间复杂度为()

  AO(N)BO(NlogN)CO(N²)DO(N²logN)

1回答
2019-05-01 20:53
我要回答
请先登录
任士焱

  答案是B根据条件递推:T(N)=N/2+2T(N/2)=N/2+2*(N/4+2T(N/4))=N/2+N/2+4T(N/4)=N/2+N/2+N/2+8T(N/8)=.可见N每次除2,是按log递减的,所以在logN次以后减为1,又因为T(1...

2019-05-01 20:54:38

最新问答

推荐文章

猜你喜欢

附近的人在看

推荐阅读

拓展阅读

  • 大家都在看
  • 小编推荐
  • 猜你喜欢
  •