作者assassin88 (AI)
看板Grad-ProbAsk
标题[理工] [DS]-Fibonacci Search
时间Sat Jan 2 22:11:59 2010
假设 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
1F：推 abien:树没画完.. 01/02 22:21
2F：→ abien:画完之後去观察这颗tree 想想AVL tree的定理 01/02 22:25
3F：→ assassin88:不是很懂耶..分成左(F7=13)跟右(F8=21) and then? 01/02 22:38