求解递推关系式T(n) = T(n − 2) + n log n的疑问求助
求解递推关系式T(n) = T(n − 2) + n log n的疑问求助
大家好,我现在卡在一个递推关系式的求解上,想请教一下各位大佬。我要解决的递推式是:T(n) = T(n − 2) + n log n
初始条件是 T(0) = T(1) = 1。
之前我处理过类似的递推,比如T(n) = T(n-1) + log n的时候,我可以把它展开成:T(n) = T(n-i) + log(n) + log(n-1) + ... + log(n-i+1)
然后令n-i = 1,就能进一步计算求和了。
但现在这个递推式是T(n-2),每次步长是2,我就有点懵了,不知道这种情况下怎么展开n log n这一项,也不清楚这种步长为2的递推该怎么处理才对。有没有大佬能给我指个方向呀?
备注:内容来源于stack exchange,提问作者lobsterj
相关产品推荐
相关产品推荐

