转到斐波那契数列生成器

Question

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...

Answer 1

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.