「アウトプットと言う名の備忘録@Texas」

日本じゃない何処かの脳筋パイソニスタによる何かしらの走り書き

【海外エンジニア転職活動】Coding Interview鍛錬: 01.Recursion - フィボナッチ数(Fibonacci numbers)

問:フィボナッチ数(一般にF(n)と表記)

ja.wikipedia.org
のn番目の数を求めよ。

このような数式で表される。

f(0) = 0, f(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

例えばn=8の時、
答えは13

0, 1, 1, 2, 3, 5, 8, 13, 21

早速解いていく

f:id:At_sashimi_py:20220222143502p:plain
早速解いていくよ

再帰の問題で定番のフィボナッチ。
今回も前回に引き続きRecursion(再帰で攻めていく!
atsashimipy.hatenablog.com

1. 最初の0, 1 はそのまま。
2. それ以降はfib自身を繰り返す関数をコードしていく。

class Solution:
    def fib(self, n: int) -> int:
        
        if n == 0:
            return 0
        elif n == 1:
            return 1
        
        return self.fib(n - 1) + self.fib(n - 2)

秒!!

いやいや、これは流石に定番すぎー!

...と思いきや、

Time Complexity は O(2N)

秒で解けても、実際にこのコードでは

再帰の各レベルでの必要な演算量が、nに近づくにつれて指数関数的に増加してしまう!

f:id:At_sashimi_py:20220222143333p:plain
圧倒的に遅い...


企業にもよると思うけど、これでクリアってところもあれば
O(N)で解いてねっていうところもあるかもしれないので、

次回

Memoization

乞うご期待!

ありがとうございましたー!