英文:
Go Fibonacci sequence generator
问题
这是我的斐波那契数列生成器：
package main
import "fmt"
func main() {
for i, j := 0, 1; j < 100; i, j = i+j,i {
fmt.Println(i)
}
}
它可以正常工作，但我不知道如何改进它，我希望能得到更专业的方法，谢谢...
英文:
This is my fibonacci generator:
package main
import "fmt"
func main() {
for i, j := 0, 1; j < 100; i, j = i+j,i {
fmt.Println(i)
}
}
It's working, but I don't know how can I improve it, I'd like more expert approaches about it, Thanks...
答案1
得分: 2
我假设你在谈论改进时间复杂度（而不是代码复杂度）。
你的解决方案以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个斐波那契数，从理论上讲，你已经达到了最好的时间复杂度。
英文:
I assume you are talking about improving the time complexity (and not the code complexity).
Your solution computes the Fibonacci numbers in O(n) time. Interestingly, there exists an O(log n) solution as well.
The algorithm is simple enough: Find the nth power of matrix A using a Divide and Conquer approach and report (0,0)th element, where
A = |1 1 |
|1 0 |
The recursion being
A^n = A^(n/2) * A^(n/2)
Time complexity:
T(n) = T(n/2) + O(1) = O(logn)
If you think about it with a piece of paper, you'd find that the proof is simple and is based upon the principle of induction.
If you still need help, refer to this link
NOTE: Of course, the O(logn) time is true only if you want to find the nth Fibonacci number. If, however, you intend to print ALL of the n fib numbers, theoretically, you can not have a better time complexity than you already have.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论