質問編集履歴
2
fibrecursiveのプログラムを修正しました。
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -52,7 +52,7 @@
|
|
|
52
52
|
|
|
53
53
|
else:
|
|
54
54
|
|
|
55
|
-
return fib(n-1) + fib(n-2)#n-2
|
|
55
|
+
return fibrecursive(n-1) + fibrecursive(n-2)#n-2
|
|
56
56
|
|
|
57
57
|
|
|
58
58
|
|
1
試したことの追記
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -94,11 +94,39 @@
|
|
|
94
94
|
|
|
95
95
|
print(ans)
|
|
96
96
|
|
|
97
|
+
```
|
|
97
98
|
|
|
99
|
+
|
|
100
|
+
|
|
101
|
+
###試したこと
|
|
102
|
+
|
|
103
|
+
数学的に考えると
|
|
104
|
+
|
|
105
|
+
再帰ありのフィボナッチ数列は以下の漸化式になり（cはnに関係ない定数）
|
|
106
|
+
|
|
107
|
+
|
|
108
|
+
|
|
109
|
+
O(n) = c (n=0 or 1のとき)
|
|
110
|
+
|
|
111
|
+
|
|
112
|
+
|
|
113
|
+
O(n) = O(n-1) + O(n-2) + c (n>=2のとき）
|
|
114
|
+
|
|
115
|
+
|
|
116
|
+
|
|
117
|
+
n>=2の時のO(n)を展開すると以下のようになり、再帰ありのフィボナッチ数列の計算量が`O(n)`なのか`O(2^n）`なのかもしくは別の記述になるのか更にわからなくなってしまいました。
|
|
98
118
|
|
|
99
119
|
```
|
|
100
120
|
|
|
121
|
+
T(2) = T(2-1) + T(2-2) + c = c + c + c = 3c
|
|
101
122
|
|
|
123
|
+
T(3) = T(3-1) + T(3-2) + c = T(2) + c + c = 5c
|
|
124
|
+
|
|
125
|
+
T(4) = T(4-1) + T(4-2) + c = T(3) + T(2) + c = 9c
|
|
126
|
+
|
|
127
|
+
T(5) = T(4) + T(3) + c = 15c
|
|
128
|
+
|
|
129
|
+
```
|
|
102
130
|
|
|
103
131
|
|
|
104
132
|
|