fibonacci number

fibonacci numberGogolang2020年8月23日

【高速】フィボナッチ数列をビネの公式を使いGoで実装する

結論 O(log (n))となり 1000項目めを求めるには0.000199s 10000項目めは0.000405sで求められました。完成品 https://github.com/kooooohe/fibonacci/blob/master/main.g [https://github.com/kooooohe/fibonacci/blob/master/main.go]o 通常の再帰を使った簡単な解き方 fib_blog_1.goGitHub Gist: instantly share code, notes, and snippets.Gist 262588213843476 [https://gist.github.com/kooooohe/17818f61bcfe287eb2709466eaccbf7f]func fib(num int) int { if num <= 1 { return num } return fib(num-2) + fib(num-1) } これだとO(2^n)となるためかなり遅い。 ※メモ化については今回は割愛