kinabaさんのアルゴリズムコンテストの挑み方を真面目に読み直していると、こんな一文が。
自分の持っている計算機が、どのくらいのスピードで「計算」できるか、ご存じでしょうか？
感覚的には億のオーダー、つまり 10^8 超えたらGCJ Largeでは黄色信号かなあ(制限時間8分のため)、というぐらいには理解しているのですが、確かに正確な性能はわかりません。
というわけで測ってみることにしました。
測定環境
使用言語
測定結果
大体表の通り。
時間はほぼ全てリニアに伸びてます。
ループ回数が10倍になったら単純に10倍すればいいです。
| 測定内容 | ループ回数 | 時間[sec] |
| 1〜Nまでの和 | 10^7 | 4.55 |
| 1/N〜N/Nまでの和(全てfloat) | 10^7 | 12.24 |
| 乱数生成 | 10^7 | 22.92 |
| ランダムな配列のソート | 10^6 | 1.29 |
| 配列へのappend | 10^7 | 4.33 |
| [0]*nによる配列の生成 | 10^8 | 0.85 |
他に測定したい項目があれば随時追加。
考察
はっきりとわかったのは、「一問題で 10^8 は黄信号ではなくアウト」ということです。
テストケースで 10^1〜10^2 とられる以上、一つの問題を解くには 10^6〜10^7 以上の計算量をかけちゃいけないということです。
つまり、n=10^3 だったらO(n^2) が計算量の限界ですし、n=10^2 だったら O(n^3) が限界です。
せっかく解いた Large でタイムアウトとか目も当てられないので、このあたりの計算量だけは常に頭に叩き込んでおきたいところです。
あと、メモリ空間の限界も忘れちゃいけません。
配列の生成は 10^8 で限界で、 10^9 ではダメでした(搭載メモリ量からすれば当たり前)。
何でもかんでもメモリ上に確保しないよう気をつけなければなりません。
