斐波拉契O(1)算法

发表于 | 更新于 | 分类于 ， | 阅读次数：
本文字数： 396 | 阅读时长 ≈ 1 分钟

第n个斐波拉契数的O(1)算法

1
2
def fib(n):
    return (4 << n*(3+n)) // ((4 << 2*n) - (2 << n) - 1) & ((2 << n) - 1)

递归算法

1
2
3
def fib_recursive(n):
    if n < 2: return 1
    return fib_recursive(n - 1) + fib_recursive(n - 2)

O(n)算法

1
2
3
4
5
def fib_iter(n):
    a, b = 1, 1
    for _ in xrange(n):
        a, b = a + b, a
    return b

关于O(1)算法的资料

0%