斐波那契散列法

2016-09-07 本文已影响0人 allanYan

斐波那契散列法本质上是一个乘法散列法，特殊的是它采用一个特殊的乘数,选择的这个乘数和黄金分割比例密切相关；

黄金分割比例

给定两个正数x和y,如果x/y=(x+y)/x,则

黄金分割比例
被叫做黄金分割比例;
![](http://www.forkosh.com/mathtex.cgi?%20\Large%20{\frac xy}={\frac {x+y}x})
${x^2-xy-y^2=0}$
![](http://www.forkosh.com/mathtex.cgi?%20\Large%20\phi={\frac xy})
${\phi}^2-{\phi}-1=0$
![](http://www.forkosh.com/mathtex.cgi?%20\Large%20{\phi}={\frac {1+\sqrt5}2})
在斐波那契散列法中，我们关心的并不是黄金分割比例，而是它的倒数：
${\phi^{-1}}=0.6180339887$
$a=2^w*{\phi}^{-1}$

位数(w)	乘数	备注
16	40503	0.6180339887*2^16=40503.4754834432
32	2654435769	0.6180339887*2^32=2654435769.2829335552
64	11400714819323198485	0.6180339887*2^64=11400714818402800990.5250107392

斐波那契散列法

黄金分割比例

猜你喜欢

热点阅读