Fibonacci 分划代替二分法次数增加 44% 左右

前几天碰到一道题目，用加减法实现除法。本来是可以用二分法快速逼近的，不过二分法没办法避免递归或者说对数的空间复杂度。而使用 fibonacci 数列则可以不递归，也可以在常数空间复杂度内完成。

不过 fibonacci 数列到底是比 2 的指数慢。但是慢多少呢？这个可以计算出来。fibonacci 数列是 φ（φ=(2^0.5+1)/2≈1.618034）的指数。令 2^n = φ^k，则可求得 k/n = ln2/lnφ，约等于 1.440420。
可以用程序验证：

fib_prev = 1
fib = 1
fib_n = 1

x = 1

for i in range(1, 100000, 1):
    x += x

    while fib < x:
        t = fib
        fib += fib_prev
        fib_prev = t

        fib_n += 1

    if i % 1000 == 0:
        print fib_n * 1.0 / i


参考：
"Binomial heaps, Fibonacci heaps, and applications", Dan Feldman, ~dannyf/ds09/fibo-ds2008.ppt, date: 2009-05-05