作者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