斐波那契数列 递归与非递归算法时间复杂度分析

第二种优化算法：（递归） Fib(int n){ if(n==0||n==1)   return 1;    else   return Fib(n-1)+Fib(n-2); }

二种优化算法:（非递归）

{ for(i=n;i>=0;i++){ if(i==0||i==1) F=1; else  F+=2*i-3; } return F; }

剖析：令T(N)为涵数Fib(N)的运作時间。   若N=0或是N=1,则运作时间某一常标值，即第一行上做分辨及其回到常用的時间。由于常数不关键，因此人们能够说T(0)=T(1)=1.   针对N的另一个好多个值的运作時间，则相对性于标准情况的与运算時间来开展量度。若N>2,则实行该涵数的时间 第一行的常数工作中 + 第三行的工作中。第三行的工作中是由多次加法和2次函数调用构成。因为函数调用并不是简易地与运算。则人们必需根据他们自身来开展剖析。     初次：Fib(N-1)进而依照T的界定，他必须T(N-1)个時间模块。 再次：与初次相近，推测它必须T(N-2)个時间模块。这时候总体時间要求为 T(N-1)+T(N-2)+2 至少2为第一行的工作中，再加第三行的加法工作中。    因此针对N>=2，Fib(N)的時间关系式为 T(N)=T(N-1)+T(N-2)+2 又由于Fib(N)=Fib(N-1)+Fib(N-2) 因此由归纳法知Fib(N)<(5/3)^N 针对N>4,Fib(N)>(3/2)^N;因此运作速率以指数值速率增长。

二种方式:根据对键入的n值开展解决，其第一行for句子为线形时间单位，而以后的句子中分別能加与运算，减与运算及其乘法与运算。几种与运算的時间和为 3，其在for句子中而循环系统频次为n，因此其时间复杂度为O（3n），即O（n）。