/var/log/messages

Oct 22, 2017 - 1 minute read - Comments - Go

昨日の PR について

O(n^2) ではないのではないか、と思いはじめている件。

最初の実装以下でした。

func Fib(n int) int {
    if n == 0 || n == 1 {
        return n
    }
 
    return Fib(n-1) + Fib(n-2)
}

寝惚けててスルーしてたのですがよくよく見てみるに、どう考えてもこれは O(n^2) ではないよね。。

その後

コメント回答頂いています。やりとりは略するとして面白いポインタを教えてもらったのでこちらでも紹介を。

さらに追記

N よりは 2N の方が断然良い、とのことなので測定してみたいですね。

pull request もらった 碁盤の構成が面白い件

comments powered by Disqus