数据结构与算法

来源：百度知道 编辑：UC知道 时间：2024/05/04 08:51:22
哪位gg、jj帮忙做做
斐波那契数列定义为： 给出一个计算第 个斐波那契数的非递归的算法，指出算法中的基本操作，分析你的算法的时间复杂性并用大O记法表示之

int fib(int n)
{
int a,b,sum,i;
a=b=1; i=3; sum=a+b;
if (n==1||n==2) return 1;
while (i<=n)
{
a=b;
b=sum; \递归展开\
sum=a+b;
i++;
}
return sum;
}

function fibo(n:longint):longint;
var
a,b,c,i:longint;
begin
a:=1; b:=1;
if (n=1) or (n=2) then exit(1);
i:=3; c:=a+b;
while i<n do
begin
a:=b;
b:=c;
i:=i+1;
c:=a+b;
end;
exit(c);
end;
递推算法，时间复杂度为 O(n)