100题_16 O(logn)求Fibonacci数列
时间：2011-03-08 来源：小橋流水
我们很容易想到递归和循环的方法，最快是O(n)的
对于O(lgn)的解法，我们要用到公式：
f(n) f(n-1) 1 1 (n-1)
f(n-1) f(n-2) = 1 0
a^n = a^(n/2)*a^(n/2) 或 a^[(n-1)/2]*a^[(n+1)/2]
代码就不写了，很水的
相关阅读 更多 +
时间：2011-03-08 来源：小橋流水
我们很容易想到递归和循环的方法，最快是O(n)的
对于O(lgn)的解法，我们要用到公式：
f(n) f(n-1) 1 1 (n-1)
f(n-1) f(n-2) = 1 0
a^n = a^(n/2)*a^(n/2) 或 a^[(n-1)/2]*a^[(n+1)/2]
代码就不写了，很水的
