質問編集履歴
2
fibrecursiveのプログラムを修正しました。
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -25,7 +25,7 @@
|
|
|
25
25
|
elif n == 1:
|
|
26
26
|
return 1 #1
|
|
27
27
|
else:
|
|
28
|
-
return
|
|
28
|
+
return fibrecursive(n-1) + fibrecursive(n-2)#n-2
|
|
29
29
|
|
|
30
30
|
if __name__ == '__main__':
|
|
31
31
|
ans = fib(6)
|
1
試したことの追記
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -46,9 +46,23 @@
|
|
|
46
46
|
if __name__ == '__main__':
|
|
47
47
|
ans = fib(6)
|
|
48
48
|
print(ans)
|
|
49
|
+
```
|
|
49
50
|
|
|
51
|
+
###試したこと
|
|
52
|
+
数学的に考えると
|
|
53
|
+
再帰ありのフィボナッチ数列は以下の漸化式になり（cはnに関係ない定数）
|
|
54
|
+
|
|
55
|
+
O(n) = c (n=0 or 1のとき)
|
|
56
|
+
|
|
57
|
+
O(n) = O(n-1) + O(n-2) + c (n>=2のとき）
|
|
58
|
+
|
|
59
|
+
n>=2の時のO(n)を展開すると以下のようになり、再帰ありのフィボナッチ数列の計算量が`O(n)`なのか`O(2^n）`なのかもしくは別の記述になるのか更にわからなくなってしまいました。
|
|
50
60
|
```
|
|
61
|
+
T(2) = T(2-1) + T(2-2) + c = c + c + c = 3c
|
|
62
|
+
T(3) = T(3-1) + T(3-2) + c = T(2) + c + c = 5c
|
|
63
|
+
T(4) = T(4-1) + T(4-2) + c = T(3) + T(2) + c = 9c
|
|
64
|
+
T(5) = T(4) + T(3) + c = 15c
|
|
65
|
+
```
|
|
51
66
|
|
|
52
|
-
|
|
53
67
|
### 補足情報（FW/ツールのバージョンなど）
|
|
54
68
|
python3.6
|