Fibonacci 斐波那契數列

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377 ,610, 987……

遇到遞迴最好畫出弟回數

            f(20)
           /     \ 
        f(19)   f(18)
       ...           ...
      /  \           /  \   
    f(1) f(2)       f(1) f(2)

1. 迴圈版本

// Fib : iterative 迴圈
func FibIterative(n int) int {
    var result = []int{0, 1}

    for i := 2; i <= n; i++ {
        a := result[i-1]
        b := result[i-2]
        result = append(result, a+b)
    }
    return result[n]
}

2. 遞迴版本

O(2^n)

// Fibrecur : recursive 遞迴 O(2^n)
func Fibrecur(n int) int {
    if n < 2 {
        return n
    }

    return Fibrecur(n-1) + Fibrecur(n-2)
}

3. 備忘錄遞迴

O(n) 重疊子問題, 如果用暴力窮舉的話,效率會極低, 所以需要memory table 或 DP table 來優化窮舉過程遞迴的複雜度計算 = 子問題個數乘以解決一個子問題需要的時間

var cache = map[int]int{}

func memoize(fn func(int) int) func(int) int {
    return func(args int) int {
        if _, vok := cache[args]; vok == true {
            // 已計算過
            return cache[args]
        }

        result := fn(args) // 跑 Fibrecur(args)
        cache[args] = result
        return result
    }
}

// Fibmem2 : memoization 拉出遞迴function
func Fibmem2(n int) int {
    result := memoize(Fibrecur)
    return result(n)
}

4. DP table (最佳解)

method 1

// the dp table
var memo = map[int]int{}

// FibDP : 
// 比較快!
func FibDP(n int) int {
    // 如果有cached 直接回傳
    if v, vok := memo[n]; vok == true {
        // cached
        return v
    }

    if _, vok := memo[0]; vok == false {
        // 沒cache
        memo[0] = 0
    }

    if _, vok := memo[1]; vok == false {
        // 沒cache
        memo[1] = 1
    }

    for i := 2; i <= n; i++ {
        if _, vok := memo[i]; vok == false {
            // 沒cache
            a := memo[i-1]
            b := memo[i-2]
            memo[i] = a + b
        }
    }

    // return FibDP(n-1) + FibDP(n-2)
    return memo[n]
}

method 2: 狀態壓縮

將空間複雜度降為 O(1) 一般來說一個二維的DP table壓縮成一維, 即把空間複雜度從 O(n^2) 壓縮成 O(n)

// the dp table
func FibDPStateCompression(n int) int {
    if n == 0 {
        return 0
    }
    if n == 2 || n == 1 {
        return 1
    }

    prev := 1
    curr := 1

    for i := 3; i <= n; i++ {
        sum := prev + curr
        prev = curr
        curr = sum
    }
    return curr
}

Benchmark

// go test -benchmem -run=none MyGoNote/Interview/algorithms/Fibonacci -bench=.
goos: darwin
goarch: amd64
pkg: MyGoNote/algorithms/Fibonacci
cpu: Intel(R) Core(TM) i5-8259U CPU @ 2.30GHz
BenchmarkFib-8                           3409812               435.8 ns/op           992 B/op          5 allocs/op
BenchmarkFibrecur-8                            3         391624567 ns/op               0 B/op          0 allocs/op
BenchmarkFibmem-8                       106473912               11.56 ns/op            0 B/op          0 allocs/op
BenchmarkFibmem2-8                      28739854                49.79 ns/op           16 B/op          1 allocs/op
BenchmarkFibmemStateCompression-8       123085564               10.72 ns/op            0 B/op          0 allocs/op
PASS
ok      MyGoNote/algorithms/Fibonacci   12.090s

Fibonacci