推 abien:樹沒畫完.. 01/02 22:21
→ abien:畫完之後去觀察這顆tree 想想AVL tree的定理 01/02 22:25
→ assassin88:不是很懂耶..分成左(F7=13)跟右(F8=21) and then? 01/02 22:38
假設 n=33 筆，Fib. search decisio tree 如下：
21
/ \ -----1
13 29
/ \ / \ -----2
08 18 26 32
/ \ / \ / \ /\ -----3
05 04 16 20 24 28 31 33
/ \ / / \ \ / -----4
15 17 19 23 25 27 30
/ / -----5
14 22
樹也太難打..= =
這是洪X上課所講的例題，
先找出 Fa => m = (n+1) - Fa => Fa = 34，
不過不懂的是..為什麼最多比較次數是七次？
34不是 Fib.數列 的第九項嗎，所以要九次？
換種看法，如果從樹的root作top-down下來這樣也頂多五次？
還是說我觀念錯誤了..還麻煩指教了><
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.57.105.199