如果设F(n)为该数列的第n项(n 属于N+)。那么这句话可以写成如下形式: F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2)(n>= 3), 请实现该函数F(n)的求解,并给出算法复杂度,要求算法复杂度小于O(n^2)。
int fun(int n){
if(n==1)
return 1;
if(n==2)
int i1 = 1 ;
int i2 = 1;
int a = 0;
for(int i = 3 ; i <=n ; i++){
a=i1+i2;
i1=i2;
i2=a;
}
return a;