首页 > 代码库 > Fibonacci 0,1,1,2,3,5,8…… 数列的实现
Fibonacci 0,1,1,2,3,5,8…… 数列的实现
Fibonacci 0,1,1,2,3,5,8…… 数列的实现
下面是对这个数列的两种算法实现,一种是递归实现,一种是多项式算法实现!在第一种情况下,当n值达到一定大小时,计算机的运行时间明显加大,对其的改进的第二种方法说是秒杀了第一种算法!
递归算法的时间复杂度是指数级别
下面是对这个数列的两种算法实现,一种是递归实现,一种是多项式算法实现!在第一种情况下,当n值达到一定大小时,计算机的运行时间明显加大,对其的改进的第二种方法说是秒杀了第一种算法!
递归算法的时间复杂度是指数级别
多项式算法的时间复杂度是线性增长级别
package review; public class Fibonacci { public static void main(String args[]){ int n=200; //多项式发 fib1(n); //递归法 for(int i=0;i<=n;i++) { System.out.println(fib(i)); } } //递归法(指数级复杂度) public static int fib(int n){ if(n==0) { return 0; }else if(n==1) { return 1; }else { return fib(n-1)+fib(n-2); } } //多项式发(线性复杂度) public static void fib1(int n){ if(n==0){ System.out.println(0); } int a[]=new int[n+1]; a[0]=0; a[1]=1; System.out.println(a[0]); System.out.println(a[1]); for(int i=2;i<=n;i++){ a[i]=a[i-1]+a[i-2]; System.out.println(a[i]); } } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。