第1个回答 2024-03-20
所谓扩展递归，就是根据递归式不断迭代，直到结果可求
1. T(n)=3·T(n-1)=3²·T(n-2)=……=3ⁿ⁻¹·T(1)=4·3ⁿ⁻¹
2. T(n)=2·T(n/3)+n=2·[2·T(n/3²)+n/3]+n=2²·T(n/3²)+n·(2/3+1)
=2²·[2·T(n/3³)+n/3²]+n·(2/3+1)=2³·T(n/3³)+n·[(2/3)²+(2/3)+1]
=...=2ᵏ·T(n/3ᵏ)+n·[(2/3)ᵏ⁻¹+(2/3)ᵏ⁻²+...+(2/3)+1]=2ᵏ·T(n/3ᵏ)+n·[1-(2/3)ᵏ]/(1-2/3)
n为3ᵏ的形式才能得到T(1)，令n=3ᵏ，则k=log(n)/log(3)=log₃n
T(n)=2^(log₃n)·T(1)+3n·[1-(2/3)ᵏ]=n^(log₃2)+3n·[1-(2/3)^(log₃n)]
=n^(log₃2)+3n·[1-n^[log₃(2/3)]=n^(log₃2)+3n·[1-n^(log₃2-1)]
=n^(log₃2)+3n·[1-n^(log₃2)/n]
注：上面用到了对数的换底公式，即a^[logb(n)]=n^logb(a)
参考链接：求解递归方程的一些方法与例题
相似回答