[理工] [DS]recursive tree

[jim055006 (好崩潰)]

Given positive constants:c1,c2,...,ck,c', assume that
T(n)<=T(c1*n)+T(c2*n)+...+T(ck*n)+c'n.
If these constants c1+c2+...+ck=1, prove T(n)=O(nlgn).


小弟用遞迴樹去解得 ,  其中c1+


                         c'n                                           c'n
                      ∕ ｜    ＼
                     ∕  ｜      ＼
                c'c1n   c'c2n .... c'ckn                               c'n
                  ∕     ｜          ＼
                 :       :              :                               :
                 :       :               :
               ∕        ｜                ＼                           :
               1-----------------------------1


接著要去證明

Σlevel cost <= n*最大高度

可是我卻不知道最大高度要怎麼假設ㄝ?

有請高手幫忙解惑一下
鋼溫!!!

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 223.138.226.199
推 gskman:theta (log n)
→ jim055006:怎麼推算的呢??...
→ gskman:你不是都畫出來了嗎@@
→ gskman:看不出來的話 你就不失一般性設 ci=1/k for all i=1,..,k
推 gskman:樹高就是以k為底的log n ,k為常數,就是theta(log n)
不是應該要設c'n(ck)^h=1....然後求h嗎??
我h求不出來= ="
※ 編輯: jim055006       來自: 223.138.226.199      (12/07 22:39)
→ gskman:n*(ck)^h=1<=>n=(ck)^h<=>(兩邊取log)log n=h*(log ck)
→ gskman:ck為常數 log ck為常數 => h = theta(log n)
不好意思
請問為什麼
n*(ck)^h=1 可以變成 n=(ck)^h
再一次感謝G大那麼熱心鋼溫!!
※ 編輯: jim055006       來自: 223.138.226.199      (12/07 22:54)
→ gskman:呃...我打錯了...是除XD
g大你的意思是說
   n
-------=1
(ck)^h

啊!!我懂了...我突然頓悟了XD
太感謝你了G大

※ 編輯: jim055006       來自: 223.138.226.199      (12/07 23:00)
※ 編輯: jim055006       來自: 223.138.226.199      (12/07 23:01)
※ 編輯: jim055006       來自: 223.138.226.199      (12/07 23:02)
→ gskman:我用的是k啦 就比較不容易搞混 n/(k^h)=1,這樣可以接受嗎?
→ jim055006:感謝....大推!!
→ sneak: 你不是都畫出來了嗎@@ https://daxiv.com