【递归算法时间复杂度】考研题,求时间复杂度,请说明下理由,假定问题规模为N时...
答案:2 悬赏:70 手机版
解决时间 2021-03-09 17:42
- 提问者网友：未信
- 2021-03-08 18:48
【递归算法时间复杂度】考研题,求时间复杂度,请说明下理由,假定问题规模为N时...
最佳答案
- 五星知识达人网友：雪起风沙痕
- 2021-03-08 18:55
【答案】 答案是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)=1,
所以一共有 logN 个 N/2
也就是 N/2 * logN
所以答案是 O(NlogN) .
根据条件递推：
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)=1,
所以一共有 logN 个 N/2
也就是 N/2 * logN
所以答案是 O(NlogN) .
全部回答
- 1楼网友：独行浪子会拥风
- 2021-03-08 20:20
好好学习下
我要举报
如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
点此我要举报以上问答信息
大家都在看
推荐资讯