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

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) .