费波那契数列算法

import datetime#由于斐波那契特性前两首0,1，其后各项均为之前两数之和可知,时间复杂度O(n)def fib(n):fibs=[0,1]for i in range(n-2): #开始两项已知fibs.append(fibs[-2]+fibs[-1])return fibs[-1]#迭代实现,时间复杂度O(n)def fib1(n):a,b = 0,1for i in range(n-1):a,b= b,a+breturn a #递归算法实现，其中n=0返回0,n=1返回1，n>=2返回之前两项之和,时间复杂度O(nlgn)def fib12(n):if n == 0:return 0elif n == 1:return 1else:return fib1(n-2)+fib1(n-1)# 递归进行初始化O(nlgn)def fib3(n):init = {0: 0, 1: 1}if not n in init:init[n]=fib2(n-2)+fib2(n-1)return init[n] print(datetime.datetime.now())#print("1\t"+str(fib(10000))) #0.1Sprint(datetime.datetime.now())print("2"+str(fib3(10000))) #0.8sprint(datetime.datetime.now())#print("3\t"+str(fib1(30))) #3.4sprint(datetime.datetime.now())#print("4\t"+str(fib2(30)) #7.1sprint(datetime.datetime.now())

class Ideone{public static void main (String[] args) throws java.lang.Exception{int fibnum=fib1(1000);System.out.println(fibnum);}//递归算法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 int fib1(int n){int a=0,b=1,temp=0;for(int i=0;i<n;i++){temp=a;a=(a+b);b=temp;}return a;}}

#include <stdio.h>int fib(int n);int main(void) {// your code goes hereint fibnum=fib1(10);printf("%d",fibnum);return 0;}
//递归算法int fib(int n){if(n==0) return 0;else if (n==1) return 1;else return fib(n-1)+fib(n-2);}

//非递归算法int fib1(int n){int a=0,b=1,temp=0;for(int i=0;i<n;i++){temp=a;a=(a+b);b=temp;}return a;}

public class Test{public static void Main(){// your code goes hereint fibnum=fib1(10);Console.WriteLine(fibnum);}
//递归算法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 int fib1(int n){int a=0,b=1,temp=0;for(int i=0;i<n;i++){temp=a;a=(a+b);b=temp;}return a;}}