轉到斐波那契序列發生器

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）解決方案。

的算法是很簡單：使用第一個元素分治方法和報告（0,0），其中

A = |1  1 | 
    |1  0 | 

遞歸是

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

查找矩陣A的n次冪

時間複雜度：

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

如果你想一張紙，你會發現t他的證據很簡單，並且基於歸納原理。 如果您仍需要幫助，請參閱this link

注：當然，O（LOGN）時間是真實的，只有當你想找到的第n個Fibonacci數。但是，如果打算打印所有的光纖編號，理論上講，你的複雜時間不會比現有的複雜。