遞歸實現(xiàn)斐切那波數(shù)列
遞歸實現(xiàn)的斐波那切數(shù)列的時間復(fù)雜度是O(2^n)
public static int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
斐切那波數(shù)列的優(yōu)化
此時的時間復(fù)雜度時O(n)
public static int fib(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;
}
