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

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

编程入门hacker2019-05-29 10:38:4915320A+A-

第二种优化算法:(递归) 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)。


点击这里复制本文地址 以上内容由黑资讯整理呈现,请务必在转载分享时注明本文地址!如对内容有疑问,请联系我们,谢谢!

支持Ctrl+Enter提交

黑资讯 © All Rights Reserved.  
Copyright Copyright 2015-2020 黑资讯
滇ICP备19002590号-1
Powered by 黑客资讯 Themes by 如有不合适之处联系我们
网站地图| 发展历程| 留言建议| 网站管理