DSA——斐波那契笔记

递归效率过低

用迭代。

g=f+g;

f=g-f;

先写几个
f(0)+f(1)=f(2)
f(1)+f(2)=f(3)
f(2)+f(3)=f(4)

令每个式子的第一项为f,第二项为g

即 f(n-2)---f,f(n-1)----g

能够很容易得到

g=f+g;

f=g-f;