54891


再帰ありとなし（for文）でn番目のフィボナッチ数を求めるプログラムをpython3.6で書いています。  
プログラムの時間計算量をオーダ記法で書くために、プログラム上で確認する方法を探しています。

現在は目視で  
再帰ありだとO（1+1+n-2)=O(n)  
再帰なしだとO(1+1+3*n)=O(n)  
と計算量を考えています。

しかし、[フィボナッチ数列のアルゴリズムと計算量の参考Webページ](http://www.aoni.waseda.jp/ichiji/2012/java-01/java-14-3.html)では、  
再帰ありのn番目のフィボナッチ数を求めるプログラムの計算量は  
O( ((1 + sqrt(5)) / 2)n-1 )（つまりO(2^n)？）と書かれています。

現在目視で行っている計算量計算のどこが間違っているのか、そしてそれはプログラムで何かを実装することで確認可能なのか教えていただきたいです。

**該当のソースコード**  
再帰あり

[code]

    def fibrecursive(n):
        if n == 0:
            return 1 #1
        elif n == 1:
            return 1 #1
        else:
            return fibrecursive(n-1) + fibrecursive(n-2)#n-2
    
    if __name__ == '__main__':
        ans = fib(6)
        print(ans)
    
[/code]

再帰なし

[code]

    def fibnormal(n):
        f = 1 #1
        x1 = 1 #1
        for i in range(2, n, 1): #3*n
            x2 = x1
            x1 = f
            f = x1 + x2
        return f
    
    if __name__ == '__main__':
        ans = fib(6)
        print(ans)
    
[/code]

**試したこと**  
数学的に考えると  
再帰ありのフィボナッチ数列は以下の漸化式になり（cはnに関係ない定数）

[code]

    T(n) = c (n=0 or 1のとき)
    
    T(n) = T(n-1) + T(n-2) + c (n>=2のとき）
    
[/code]

n>=2の時のO(n)を展開すると以下のようになり、再帰ありのフィボナッチ数列の計算量がO(n)なのかO(2^n）なのかもしくは別の記述になるのか更にわからなくなってしまいました。

[code]

    T(2) = T(2-1) + T(2-2) + c = c + c + c = 3c
    T(3) = T(3-1) + T(3-2) + c = T(2) + c + c = 5c
    T(4) = T(4-1) + T(4-2) + c = T(3) + T(2) + c = 9c
    T(5) = T(4) + T(3) + c = 15c
    
[/code]


CC BY-SA 4.0
2019-05-11T07:02:16.073
54887
2019-05-11T14:40:27.683
2019-05-11T13:03:06.057
question
python python3 アルゴリズム 数学 計算量
フィボナッチ数列の計算量について


再帰ありの場合のアルゴリズム `fibrecursive(n)` の時間計算量が O( ((1 + sqrt(5)) / 2)ⁿ )
というのは正しいです。このアルゴリズムだと O(n) にはなりません。たとえば実際に n を大きくしながらプログラムの実行時間を測れば、O(n)
じゃなさそうな結果が出ることでしょう。

質問者さんの間違えていそうな点として、まずはどういう計算に対して「時間 1」を割り振っていると仮定しているのかを確認してください。考えるべき行は
`return 1` の行ではなく `if n == 0` の行ではありませんか？ 更に `fib(n-1) + fib(n-2)` の部分の計算量を
n-2
と書かれている部分は大きな誤解をなさっていそうなのでよく考えてみてください（すいません、どのような形の誤解をなさっているのかまでは分析できませんでした）。

オーダーを求める具体的な解法としては、計算時間 T(n)
についての漸化式は三項漸化式になっているので、[特性方程式を使うなどして解けば](https://mathtrain.jp/fibonacci)一般項が求まります。一般項はおおよそ指数関数の差になりますが、O(
... ) によるオーダー記法は関数を上から抑えているので大きい方だけを取ればよく、O( ((1 + sqrt(5)) / 2)ⁿ )
になります。（この言い方でよく分からなければ、オーダー記法の定義にしたがって厳密に証明してみてください。）

なお、もっと厳しく評価すると O( fib(n) ) になります。T(n) の漸化式がフィボナッチ数列の漸化式とほぼ同じことに注目すれば、T(n) が
fib(n) で定数倍を除いて上から抑えられることが計算できます。

O( ((1 + sqrt(5)) / 2)ⁿ ) や O( fib(n) ) は O(2ⁿ) とは異なることに注意してください。O( ... )
によるオーダー表記は定数倍の違いしか無視しないため、たとえば O(2ⁿ) と O(3ⁿ)
は異なる計算量クラスになります。ちゃんとした証明はたとえば[この記事](http://unaguna.jp/article/archives/1#heading1)をご覧ください。（とはいえ
((1 + sqrt(5) / 2) は 2 より小さいので、T(n) は O(2ⁿ) にも属します。）


CC BY-SA 4.0
2019-05-11T09:58:10.793
54891
2019-05-11T14:40:27.683
2019-05-11T14:40:27.683
19110
19110
54887
answer