回答編集履歴
2
再回答
test
CHANGED
|
@@ -1,3 +1,15 @@
|
|
|
1
|
+
再帰の方は、
|
|
2
|
+
|
|
3
|
+
f(6)を求めるためにf(5)とf(4)が必要で、
|
|
4
|
+
|
|
5
|
+
f(5)を求めるためにf(4)とf(3)が必要で…
|
|
6
|
+
|
|
7
|
+
というように、数字が1下がるたびに計算するべき値が倍になります。
|
|
8
|
+
|
|
9
|
+
しかも現在のコードではf(5)を求めるために求めたf(4)を再利用できないので、必要計算量は倍々に膨れ上がるため、O(2^n)になります。
|
|
10
|
+
|
|
11
|
+
|
|
12
|
+
|
|
1
13
|
~~O( ((1 + sqrt(5)) / 2)n-1 )はO(n)です。((1 + sqrt(5)) / 2)は定数なので。~~
|
|
2
14
|
|
|
3
15
|
ごめんなさい最後のn-1は指数ですね。
|
1
修正
test
CHANGED
|
@@ -1 +1,3 @@
|
|
|
1
|
-
O( ((1 + sqrt(5)) / 2)n-1 )はO(n)です。((1 + sqrt(5)) / 2)は定数なので。
|
|
1
|
+
~~O( ((1 + sqrt(5)) / 2)n-1 )はO(n)です。((1 + sqrt(5)) / 2)は定数なので。~~
|
|
2
|
+
|
|
3
|
+
ごめんなさい最後のn-1は指数ですね。
|