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)

如果你用一张纸想一想，你会发现证明很简单，而且是基于归纳原理的。如果您仍需要帮助，请参阅此链接

注意：当然，只有当您想找到第 n 个斐波那契数时，O(logn) 时间才成立。但是，如果您打算打印所有n 个fib 数字，理论上，您的时间复杂度不会比现有的更好。