フィボナッチ数列の時間計算量をプログラムで確認する方法について

Question

前提・実現したいこと

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

発生している問題・エラーメッセージ

現在は目視で
再帰ありだとO（1+1+n-2)=O(n)
再帰なしだとO(1+1+3*n)=O(n)
と計算量を考えていますが、再帰あり・なしで同じになるのは不自然だと考えています。

実際に、フィボナッチ数列のアルゴリズムと計算量の参考Webページでは、
再帰ありのn番目のフィボナッチ数を求めるプログラムの計算量は
O( ((1 + sqrt(5)) / 2)n-1 )（つまりO(2^n)？）と書かれています。

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

該当のソースコード

再帰あり

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)

再帰なし

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)

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

O(n) = c (n=0 or 1のとき)

O(n) = O(n-1) + O(n-2) + c (n>=2のとき）

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

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

補足情報（FW/ツールのバージョンなど）

python3.6

Comments

[cateye]

>再帰あり・なしで同じになるのは不自然・・・・そう思った根拠は？　再起しようがしまいが（スタックに積むかどうかの違いなので）計算量そのものに違いが有る方がおかしいと思いますが？・・・・

[退会済みユーザー]

フィボナッチ数列のアルゴリズムと計算量の参考Webページで、再帰有無のオーダ記法が異なっていたからです。

[cateye]

「計算が速い理由」・・・と書いてありますが、実行時間ではではないですか？・・・計算量とはちがう・・・

[退会済みユーザー]

計算が速い理由とは、参考ページに書いてあったということでしょうか。

[cateye]

演習 14.4 4.Fib2 が Fib1 に較べて計算が速い理由を考えなさい．

[cateye]

今気が付いたけど、再帰版と非再帰版で回数が違いませんか？
１３と８がプリントされる・・・

[退会済みユーザー]

マルチポストしたのであれば、双方の質問を適切にコントロールして下さい。
https://ja.stackoverflow.com/questions/54887/%e3%83%95%e3%82%a3%e3%83%9c%e3%83%8a%e3%83%83%e3%83%81%e6%95%b0%e5%88%97%e3%81%ae%e8%a8%88%e7%ae%97%e9%87%8f%e3%81%ab%e3%81%a4%e3%81%84%e3%81%a6

Answer 1

再帰あり・なしで同じになるのは不自然だ

不自然ではありません。再帰そのものに計算量を左右する要因はないです。例えば階乗の計算量は再帰であろうとループであろうと計算量は同じです。

def fact(n):
    if n == 0:
        return 1
    else:
        return n * fact(n - 1)

# でも

def fact(n):
    r = 1
    for i in range(1, n + 1):
        r *= i
    return r

# でも計算量はO(n)

フィボナッチ数列の計算において計算量が違う要因は「過去に計算済みの値を何度も再計算するのか過去の結果を直ちに利用するか」といった再帰とは別の次元のことです。

再帰であっても過去の計算結果を「再度計算せずに直ちに利用する」テクニックは考えることができそれを適用すると計算量をループと同等にできます。

memo = {}

def memorize(f):
    # 1引数の関数の過去の計算結果を記憶する
    def memorizing_f(n):
        if n in memo:
            return memo[n]
        else:
            r = memo[n] = f(n)
            return r
    return memorizing_f



def fib(n):
    global count
    count += 1
    if n == 0:
        return 1
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)#n-2

count = 0
fib(5)
print(count)    # -> 15

count = 0

@memorize
def fib(n):
    global count
    count += 1
    if n == 0:
        return 1
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)#n-2

count = 0
fib(5)
print(count)    # -> 6

memorizeで用いているdictは任意のキーに対するルックアップの計算量がO(1)と期待できますので別にずるではなく本当に効率がよくなります。

Comments

[KSwordOfHaste]

> プログラムで何かを実装することで確認可能なのか

について本来はswordoneさん回答のように理論的に考えるのがよいです。しかし理論的に考えるのが難しいときは自分の回答にあるようにfib関数が実際に何度呼び出されたかをカウントするという素朴な方法でも確認できるといえましょう。こういう素朴な方法もばかにしたものではないと思います。手軽ですので。
---
しかし大きな計算をするより前に「どの程度になるか」を見通すことはやはり大事です。最終的には理論的に計算ができるようになりたいものです。

Answer 2

定義どおりに計算する方法

(1+sqrt(5))/2 は黄金比 Φ です。Φ ≒ 1.618033988749895
したがって、Φ を最も近い整数にまるめて Ｏ(2^n) とみなしてよい。

フィボナッチ数の隣合う項の比は黄金比 Φ に収束します。
実は、再帰の計算量もフィボナッチ数として指数関数的に増加する。Ｏ(fib(n))

フィボナッチ数計算の計算量

参照サイトにあるとおり、フィボナッチ数の計算方法が三種類紹介されています。

アルゴリズム	(時間) 計算量	方法
定義通り	O( ((1 + sqrt(5)) / 2)^(n-1) )	再帰
積み上げ式	O( n )	メモ化（KSwordOfHasteさんの回答）
行列計算	O( log n )	行列を使う方法

定義通り、積み上げ式はわかりました。行列計算を調べてみましょう。

補足

フィボナッチ数の一般項は、もとはオイラーが発見したそうです。（証明は難しいです）
F(n) = (Φ^n - (1-Φ)^n)/sqrt(5) ただし Φ = (1+sqrt(5))/2

一般項の近似式は次のようになります。計算量を考えるとしたらこれでいいと思います。
F(n) ≒ Φ^n/sqrt(5) 第二項(1-Φ)^n/sqrt(5)の絶対値は、最大で0.447..なので省略

第二項の性質を使って一般項を求め直すと次のようになります。これは一種のトリックです。
F(n) = floor((1/5)*Φ^n + (1/2)) floor はガウス関数。ただし正のフィボナッチ数のみ。

Comments

[退会済みユーザー]

ご回答いただきましてありがとうございます。
もはや数学の質問になってしまい恐縮ですが、参照サイトの

C(fib1(n)) = C(fib1(n-1)) + C(fib1(n-2)) + 5

C(fib1(n)) = ((1 + sqrt(5)) / 2) C(fib1(n-1))

この式展開は、C(fib1(n-2)) + 5が((1 + sqrt(5)) / 2) であるということですが、これはどのように導かれるのでしょうか。
フィボナッチ数列の一般項1/ sqrt(5){((1 + sqrt(5)) / 2)^n -((1 - sqrt(5)) / 2)^n}を用いるのでしょうか。
この部分が省略されていて、オーダ記法の証明の理解に少し困っています。

[xebme]

漸化式の解き方、隣接三項間、定数付き、で調べてください。

Answer 3

再帰の方は、
f(6)を求めるためにf(5)とf(4)が必要で、
f(5)を求めるためにf(4)とf(3)が必要で…
というように、数字が1下がるたびに計算するべき値が倍になります。
しかも現在のコードではf(5)を求めるために求めたf(4)を再利用できないので、必要計算量は倍々に膨れ上がるため、O(2^n)になります。

O( ((1 + sqrt(5)) / 2)n-1 )はO(n)です。((1 + sqrt(5)) / 2)は定数なので。
ごめんなさい最後のn-1は指数ですね。

Comments

[退会済みユーザー]

ご回答いただきましてありがとうございます。
倍の「２」というのは、f(n-1)とf(n-2)を指していますか？
f(2)のときf(1)とf(0)が必要ですが、f(1)とf(0)で計２回になりそうですが、計算量はO(4)となるのはなぜでしょうか。

[swordone]

オーダー記法による評価は割と大雑把です(もちろん、数学的にはきちんと定義されていますが)。数の増加に対して計算量にどれだけ影響があるかを示すだけのもので、計算の回数そのものをズバリ出すものではありません。
再帰によるフィボナッチ数列の計算ではnが1増えたら、計算量が｢だいたい｣2倍になるので、O(2^n)になるのです。

Answer 4

実際に測定してはいかがでしょうか?
マイクロ秒～ナノ秒精度の時計を使い、n=10,100,1000,10000等、いくつかの点を取って、それぞれのプログラムの開始前と終了後の時刻を表示するようにすれば実測値がとれます。
そうすればnに比例しているのかどうかの検証もできます。