天道酬勤,学无止境

斐波那契

0毫秒搞定斐波那契,PK掉100%提交者

目录1引言2 牛叉解法3 总结1引言对于斐波那契数列,大家学了递归应该不陌生,常规解法都是用递归实现,但是这样的时间复杂度是O(2^n)int fib(int N){if(N == 0) return 0;if(N == 1) return 1;return fib(N-1) + fib(N-2);} 我们把每调用一次函数f(n)看成执行一次,那么如果传入的参数是5,就调用了1+2+4+8+…=(2^n)-1所以很耗时间。。。。。2 牛叉解法既然斐波那契是使前一个数与在前一个数相加,那我们 我们只需要用两个参数,second表示当前累加的结果,而first始终是second的前一个数int fib(int N) {if(N<=1) return N;int second =1;int first=0;for(int i=1;i<N;i++){second+=first;first=second-first;}return second;}};时间复杂度为O(N);3 总结 =要知道算法的好坏直接决定着一个程序的好坏,算法很重要,不论是C,C++,JAVA,Python,算法都是核心==最后配上图片来源:https://blog.51cto.com/u_15166109/2718859

2021-05-13 11:19:58    分类:博客    斐波那契   算法

斐波那契数列的最优算法(O(logN))

相信大家都对斐波那契数列已经相当的熟悉了,最多两分钟就可以写出来以下时间复杂度为O(N)的代码://递归实现 long long fib(int n) { if (n =1 || n== 2) { return 1; } return (fib(n - 2) + fib(n - 1)); }或者是这样的时间复杂度为O(N),空间复杂度为O(1)://优化一:时间复杂度为O(N) long long fib(int n) { long long* fibarry = new long long[n + 1]; fibarry[0] = 0; fibarry[1] = 1; for (int i = 2; i <= n; i++) { fibarry[i] = fibarry[i - 1] + fibarry[i - 2]; } long long ret = fibarry[n]; delete fibarry; return ret; } //优化二:时间复杂度O(N) 空间复杂度O(1) long long fib(int n) { long long fibarry[3] = { 0, 1, 0 }; for (int i = 2; i <= n; i++) { fibarry[2] = fibarry[0] + fibarry[1]; fibarry[0] = fibarry

2021-05-11 23:33:59    分类:博客    数列   斐波那契   递推公式   数据结构