質問編集履歴
1
自分なりの推測を追加しました。
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -7,6 +7,26 @@
|
|
|
7
7
|
実行時間の計測には`time.Now`を用いました。
|
|
8
8
|
|
|
9
9
|
テストケースは乱数を用いて作成しています。
|
|
10
|
+
|
|
11
|
+
|
|
12
|
+
|
|
13
|
+
### 自分なりの推測
|
|
14
|
+
|
|
15
|
+
最初は再帰関数のほうが、関数参照の分遅くなると考えていましたが、実際には違いました。
|
|
16
|
+
|
|
17
|
+
2つの計算量が異なっている場合は教えてください。（計算量の違いはパット見ではわかりませんでした。）
|
|
18
|
+
|
|
19
|
+
|
|
20
|
+
|
|
21
|
+
これは計算量が同じである場合の推測ですが、`solve2`関数内の`if`において、毎回`int(math.Pow(2, float64(k))`という型変換とべき乗計算を行っているのが実行時間が遅い要因担っているのかもしれません。
|
|
22
|
+
|
|
23
|
+
|
|
24
|
+
|
|
25
|
+
しかし、それにしても2つのケースで決定的に実行速度が違うので、どこかで計算量の差異があるのではと考えています。
|
|
26
|
+
|
|
27
|
+
|
|
28
|
+
|
|
29
|
+
|
|
10
30
|
|
|
11
31
|
|
|
12
32
|
|