1樓：雲飛
直接用 f(n)=1/√5*((1+√5)/2)^n 一步出來，推導用homogeneous 遞迴公式，保證不會爆，速度槓槓的
2樓：
用斐波那契數列的通項公式，如圖：
pow函式複雜度是O(logn)，所以整體複雜度是O（logn）。不過要根據用的語言注意一些細節的方面的處理。
3樓：fcbruce
快速冪+同餘定理，10^6用O(n)的樸素演算法也夠了，還有斐波那契數列用遞迴效率實在是太低了，重複計算次數太多，而且遞迴深度大，很容易爆棧，巧妙利用資料結構和遞推會方便很多
4樓：
The Fibonacci sequence
Haskell的一些演算法，其中還有Constant-time（有條件）的演算法……
5樓：silencew
快速冪方法受教了。
數學上斐波那契數列的通項公式也早就被推導出來。
a = sqrt(5);
f(n) = round(((1+a)^n-(1-a)^n)/2^n/a);
6樓：
對 @沈周 的答案做個筆記。
1. 求菲波那契數列的第n項問題可以轉換為求矩陣的冪
2. 矩陣乘法滿足結合律，因此矩陣的冪次計算可以二分3. 可以二分且每層的計算複雜度為常量的問題，總複雜度為O(logn)
7樓：王洋子豪
如果n為1000000000，也就是1 billion的話基本上效能差距達到了600000倍很可觀
8樓：endless
這個用公式到底能不能修正誤差呢？
據說可以用矩陣加速求解。
int64
fibonacci
(int64n)
n>>=1;
x=a*
a+b*
b;y=
2*a*
b-b*
b;a=
x;b=
y;}returnra;}
9樓：王思源
寫成遞迴也沒問題，但是為了避免棧溢位，一定是要編譯器支援的尾遞迴形式，比如下面這樣寫gcc O2可以轉成迴圈
uint64_t
fib_helper
(uint64_tn,
uint64_ta,
uint64_tb)
10樓：
1000000爆棧了。請參考樓上的寫法。或者開更大的棧。
如果一定要遞迴的話……OJ常用開棧技巧。
#include
#include
const
intMaxN
=1000000
;int
fib[
MaxN+1
];intf(
intx
)int
main()
關於「我」的乙個問題？
雷雲密布 首先你想講的是乙個錯誤，因為你把1十1 2和乙個神話交集了，所以只能去佛家和一夢中去找答案了，主可能都不行，因為主很直白，所以還是道生萬物吧，用道來解就是我應隨風去，天地萬物都有靈，靈為我，我為為萬物。 這是秩的定義問題。具體用什麼定義，要看現實的需要。數只是你看世界的工具，不是 你 你 ...
關於promise的乙個問題？
追風逐月 題主最想看到的是這個 var promise new Promise function resolve,reject 3000 promise then function 3000 promise then function res then function res console.lo...
乙個關於光速？？的問題？
univeagle 假設h長30萬公里，l長40萬公里，斜邊長50萬公里，小球以光速運動，1秒鐘後小球到達平面，可原來的影子呢？還老老實實呆在那兒呢！要再過2 3秒才會消失，而此時平面上新的影子已經產生，算起來影子不是超光速，而是穿越了！而且你仔細計算會發現，不算最初的那個影子，其它影子是由近及遠傳...