计算递归方程（算法分析）

Question

我想知道如何用迭代法解决这道题

Answer 1

既然你要自己做功课，那我就给你解决一下

• T(1)=1
• T(n)=2T(n/2)+n
• n=8

n = 8
T(n) = T(8)
= 2T(8/2)+8
= 2T(4)+8
= 2*(2T(4/2)+4)+8
= 2*(2T(2)+4)+8
= 4T(2)+8+8
= 4T(2)+16
= 4*(2T(2/2)+2)+16
= 4*(2T(1)+2)+16
= 8T(1)+4+16
= 8T(1)+20
= 8*1+20
= 28