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
----------------------------------------------------------------
請各位大大 給我看法
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.171.248.120
※ 編輯: tom21tom21 來自: 118.171.248.120 (01/06 23:53)