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

[DiLegend (JOU)]

※ 引述《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:調和數列那個我知道了! 那log20=log10/2=log10-log2 嗎?
→ dunkjames:換底那個我不太懂...好像不常用! 但我知道 2^logn = n
→ dunkjames:其實你是想說出現在分母吧! 這題好像是唯一例外
※ 編輯: DiLegend        來自: 114.45.54.117        (01/27 01:07)
→ DiLegend:log20=log2*10=log2+log10  log10/2=log10-log2
→ DiLegend:如果log已經忘到這樣了 去WIKI看一下log應該比較快吧
推 dunkjames:原來WIKI可以這樣用 感謝您