費氏數列(Fibonacci numbers)#

還記得達文西密碼裡面,羅浮宮館長死前留下的密碼嗎?

其中關鍵的線索就是費氏數列!

費氏數列,又稱斐波那契數列。意思是有一列數字,最後一個數字是其前面兩個數字的相加。

我們給一個n,請您回傳費氏數列最後的數字。

Example

fib(10) -> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
answer = 55
fib(6) -> [0, 1, 1, 2, 3, 5, 8]
answer = 8

這邊我們用費氏數列來說明:

一道題目,用不同演算法所造成不同的時間複雜度。

JavaScript 解法#

先看 js 的迴圈與遞迴解

js 迴圈解#

首先我們用迴圈解:

function fib(n) {
const result = [0, 1];
for (let index = 2; index <= n; index++) {
// 倒數第一個數
const a = result[index - 1]; // or result[result.length -1]
// 倒數第二個數
const b = result[index - 2];
result.push(a + b);
}
console.log('full array: ' + result)
console.log('last number: ' + result[result.length -1])
return result[result.length -1];
}

用迴圈解,n 增加會多跑一次迴圈,因此時間複雜度是線性的(Linear Run Time)

js 遞迴解(Recursion)#

如下:

function fib(n) {
if (n < 2) {
return n;
}
return fib(n - 1) + fib(n - 2);
}

用遞迴解做了以下事情(ex: fib(5))

fib(5) 會去做 fib(4)與 fib(3)
fib(4) -> fib(3) -> fib(2) -> fib(1), fib(0) -> 1
-> fib(1) -> 1
-> fib(2) -> fib(1), fib(0) -> 1
fib(3) -> fib(2) -> fib(1), fib(0) -> 1
-> fib(1) -> 1

所以只是fib(5),共呼叫了 15 次 fib(x) ,因此在費氏數列的問題上,遞迴是時間複雜度比較差的。

因為他接近指數時間(Exponential Time)

Java 解法#

Java 迴圈解#

private static int fib1(int n) {
int theLastTwo = 0, theLastNum = 1, temp;
if (n == 0)
return theLastTwo;
for (int index = 2; index <= n; index++) {
temp = theLastTwo + theLastNum;
theLastTwo = theLastNum;
theLastNum = temp;
}
System.out.println("the Last Two " + theLastTwo);
System.out.println("the Last Number " + theLastNum);
return theLastNum;
}

Java 遞迴解#

public class FibonacciEx1 {
static private int fib(int n) {
if (n <= 1)
return n;
return fib(n - 1) + fib(n - 2);
}
public static void main(String[] args) {
System.out.println(fib(5));
}
}

此文同時發佈於鐵人賽