Question

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

假定问题规模为N时，某递归算法的时间复杂度记为T（N），已知T(1)=1，T(N)=2T(N/2)+N/2，用O表示的时间复杂度为（）
A O(N) B O(NlogN) C O(N²) D O(N²logN)

Answer 1

答案是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) 。