Re: [理工] [資結] Time Function-展開代入法

看板Grad-ProbAsk作者DiLegend (JOU)時間14年前 (2012/01/27 00:32)推噓2(2推 0噓 4→)

留言6則, 2人參與討論串2/2 (看更多)

※ 引述《dunkjames (Firefighter)》之銘言： : 1. T(n) = 2T(n/2) + n/logn : 這題我算到後面不知道該如何化簡了....答案是 n‧loglogn : -------------------------------------------------- 你也是寫到交大98還多少的吧前面有人寫出解法不過一時也找不到是哪個了令 n=2^k , k=logn T(2^k)=2T(2^(k-1) )+(2^k)/k 令A(k)=T(2^k) 所以 A(k)=2A(k-1)+(2^k)/k =4A(k-2)+ (2^k)/k +(2^k)/(k-1) =.... =2^k (A(0))+2^k(1/k + 1/(k-1)+ 1/(k-2)+...+1) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 記得是叫調和數列 =2^k (A(0))+2^k logk 而因為A(0)=0 ( A(0)=1 應該也是一樣啦反正後面比較大 ) 所以A(k) =O (2^k logk) 換回來後所以T(n)=O(nloglogn) : 2. 問一下國中數學: log(2+3) = log2 * log3 沒錯吧?! : 那log(n/2)=logn-log2 ? : log(n-2)=? : logn-2=? : log2 / log3 = log(2-3) ? : log2 / log3 = log(2/3) ? : -------------------------------------------------- : 說個你應該還記得的 log10 = log2*5 =log2+log5 然後還有log 2 / log 3 =log 2 換底公式應該是這樣吧 10 10 3 3. 該如何判定何時該用Master Method 何時只能用展開代入? 我也不知不過應該是當log出現在分母的時候吧(? 期待有強者能出面解釋 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.45.54.117 ※ 編輯: DiLegend 來自: 114.45.54.117 (01/27 00:33)

推

dunkjames

01/27 00:45, , 1^F

01/27 00:45, 1^F

→

dunkjames

01/27 00:48, , 2^F

01/27 00:48, 2^F

→

dunkjames

01/27 00:59, , 3^F

01/27 00:59, 3^F