Fibonacci numbers
文章目录
Fibonacci numbers
time complexity : O(lgN)idea
F2n-1 = Fn^2 + (Fn-1)^2
F2n = (2*Fn-1 + Fn)*Fn
If n is even then k = n/2:
F(n) = [2*F(k-1) + F(k)]*F(k)
If n is odd then k = (n + 1)/2
F(n) = F(k)*F(k) + F(k-1)*F(k-1)
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论