go - Go フィボナッチ数列ジェネレーター

Question

これは私のフィボナッチジェネレーターです:

package main

import "fmt"

func main() {
    for i, j := 0, 1; j < 100; i, j = i+j,i {
        fmt.Println(i)
    }
}

それは機能していますが、どうすれば改善できるかわかりません。より専門的なアプローチが必要です。ありがとう...

Answer 1

時間の複雑さの改善について話していると思います（コードの複雑さではありません）。

あなたのソリューションは、フィボナッチ数を O(n) 時間で計算します。興味深いことに、O(log n) ソリューションも存在します。

アルゴリズムは単純です: 分割統治法を使用して行列 A の n 乗を求め、(0,0) 番目の要素を報告します。

 A = |1     1 |
     |1     0 |

再帰は

 A^n = A^(n/2) * A^(n/2)

時間の複雑さ:

T(n) = T(n/2) + O(1) = O(logn)

紙で考えてみると、その証明は簡単で、帰納法に基づいていることがわかります。それでもヘルプが必要な場合は、このリンクを参照してください

注: もちろん、O(logn) 時間は、n 番目のフィボナッチ数を見つけたい場合にのみ真です。ただし、 n 個の fib 数のすべてを出力する場合、理論的には、既に持っているよりも優れた時間計算量を持つことはできません。