作者griffer (griffer)
看板Grad-ProbAsk
标题[理工] 离散一题递回转换
时间Wed May 13 02:43:57 2009
题目:T(n)-4T(n/3) = nlgn
=>
1.转成:A(k) - 4A(k-1) = k * 3^k * lg3 //(k)和(k-1)是下标
2.请问这题的特徵方程式要令成什麽呢?
是(d1k+d2k^2)*3^n吗?
这边看黄子嘉的书没有证特徵方程式的令法
所以有些题目不太确定要怎麽令
刚爬了一下文
这题就是 thank1984 □ [理工] 递回计算 96海大资工
的同一题
他的问题与我相同
但是推文没有解释,而是用老大定理法
请问关於特解那边有人有更好的说明吗?
谢谢回答:)
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 122.116.1.161
1F：推 whisp1222:应该不用d2k^2 k只有一次而已 所以d1k就可以 不需修正 05/13 11:05
2F：推 whisp1222:後面应该是3^k而不是3^n 05/13 11:09
※ 编辑: griffer 来自: 122.116.1.161 (05/13 12:49)
3F：→ uminchu185:k假设为do+d1k, 3^k假设为d2(3^k), 合并之後再将d0d2与 05/13 20:26
4F：→ uminchu185:d1d2重新命名c1与c2, Ap=(c1+c2k)(3^k). 05/13 20:28