推 bahamut5461:看完推!!! 01/07 23:37
※ 引述《tom21tom21 (平凡就好)》之銘言：
: http://www.lib.nsysu.edu.tw/exam/master/eng/infoe/infoe_99.pdf
: 我要問第三題 先講worse case
: best case 我要等大家討論 看看想法是否有問題 在解看看
: 我的想法 worse case "可能"是一定是 full tree & 編號越大的數值越大
: 我問過學校老師 他認為 complete tree 可以包含full tree
: 其次這樣解法比較簡單
: 首先 只有L=1
: 會印出 1次 但是會呼叫 max(p->left)*1 max(p->right)*3
: 再來 L=2
: 先印出1次（p->d）
: 在呼叫max(p->left) 然後印出一次 同理max(p->right)也一次
: （執行 max(p->left) >= max(p->right) ）
: 然後在前提假設下
: 會執行 return(p->d >= max(p->right))... 這行
: 這邊會產出2個印出
: ∴1+2+2＝5
: 現在我假設 F(L)為樹有L層
: F(1)=1 F(2)=5
: F(3)=1+F(2)+3F(2)=1+5+15=21 (1次 左子樹 3次右子樹)
: 因此F(L)=1+F(L-1)+3F(L-1)
: 解出來F(L)= (4^L -1)/3
: ----------------------------------------------------------------
: 請各位大大 給我看法
Worst Case :
因為worst case，所以complete binary tree會是full binary tree
寫成遞回式 T(L) = 4T(L-1) + 1
解出來T(L)和你的答案一樣
Best Case :
簡易版: T(L) = 3T(L-1) + 1，解出來就是 (3^L-1)/2
想很多版:
best case下，你可以把第L層(最後一層)當作只有一個點，也就是最左邊的點
然後把L-1層以上的當作一顆 高度為L-1的full binary tree
先算出T(L-1) :高度為L-1 full binary tree的部分
在去處理最後一層的唯一節點，要注意的是最後一層的唯一一個節點
在best case下，可以假設右子樹max()，都會比左子樹大
這樣左子樹每次都只會被call一次max ，在max(p->left)>max(p->right)那邊
但還有個陷阱，就是call到最後一層的時候，
由於最後一層的唯一一個節點沒有sibling，所以他會是max，因此會被print兩次
寫程式子就是T(L) = (3^(L-1)-1)/2 + 2
(L-1層full binary tree cost) (L層唯一一個結點的cost)
第二種想法當然比較嚴謹啦~雖然我覺得他應該是想考第一種而已
畢竟後面那樣要一次想對沒漏掉細節超難= =
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.218.169
※ 編輯: louis719 來自: 140.112.218.169 (01/07 01:35)
※ 編輯: louis719 來自: 140.112.218.169 (01/07 01:36)