fib函數(shù)怎樣運(yùn)算？

1.以遞歸的方式(時(shí)間復(fù)雜度是O(2^n))

public static int fib1(int i){

if(n<=1) return n;

return fib1(n-2)+fib(n-1);

}

對(duì)于fib(6)來說，第一行是fib(6) 是一個(gè) 第二行是fib(5)+fib(4) 是兩個(gè)(2^1) 第三行是fib(4)+fib(3)和fib(3)+fib(2) 是4個(gè)L (2*2) 等等 所以復(fù)雜度是O(2的n次方)

2.以普通的方式(時(shí)間復(fù)雜度是O(n)

public static int fib2(int n) {

if (n <= 1) return n;

int first = 0;

int second = 1;

for (int i = 0; i < n - 1 ; i++) {

int sum = first + second;

first = second;

second = sum;

}

return second;

}