方法一
使用動態規劃。時間複雜度為 O(n)，實際上為 O(n/2)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| package main
import (
"fmt"
)
func main() {
fmt.Println(fibonacci(10))
}
func fibonacci(n int) int {
a, b := n%2, 1
for i := 0; i < n/2; i++ {
a += b
b += a
}
return a
}
|
方法二
使用動態規劃。時間複雜度為 O(n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| package main
import (
"fmt"
)
func main() {
fmt.Println(fibonacci(10))
}
func fibonacci(n int) int {
if n < 2 {
return n
}
a, b := 0, 1
for i := 0; i < n; i++ {
next := a + b
a, b = b, next
}
return a
}
|
方法三
使用遞迴函式。時間複雜度為 O(2^n)，實際上為 O(1.6180339887^n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| package main
import (
"fmt"
)
func main() {
fmt.Println(fibonacci(10))
}
func fibonacci(n int) int {
if n < 2 {
return n
}
return fibonacci(n-2) + fibonacci(n-1)
}
|
程式碼
參考資料