/var/log/messages

debugging with sixth sense

昨日の PR について

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

最初の実装以下でした。

1
2
3
4
5
6
7
func Fib(n int) int {
    if n == 0 || n == 1 {
        return n
    }
 
    return Fib(n-1) + Fib(n-2)
}

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

その後

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

さらに追記

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

Comments