計算量のはなし

こんにちは、CPPXのP1です。 CPPXのブログモチベが低そうで悲しいところですが、今週も更新していきます。
今回は、競技プログラミングの中でも重要な考え方(？)である計算量のはなしです。

計算量の求め方ではなく、どのくらいのオーダーが何秒くらいで終わるかなーっという記事になります。
方針が立ってから実装前に、この実装で間に合うor間に合わないが分かると捗りますよね。

まず基本として、プログラミングコンテストチャレンジブック(蟻本)には、

制限時間が1秒の場合、
10の6乗　余裕を持って間に合う
10の7乗　おそらく間に合う
10の8乗　非常にシンプルな処理でない限り厳しい

とあります。(C++を基準として書かれています)

手元で試した感じでも、かなりシンプルな処理の10の7乗で

10の8乗で

くらいでした。8乗の方は1つif文を増やしただけで2秒を超えたので、現実的な処理を考えると、Atcoderの2秒制限を守るには〜10の7乗が限度といったところでしょうか。

以上を踏まえてテストケースをNとして考えると計算量の限界は

• Nが10⁶ → O(N)かO(N log N)
• Nが10⁵ → O(N log N)かO(N log² N)
• Nが3000 → O(N²)
• Nが300 → O(N³)(シンプルな処理)
• Nが100 → O(N³)
• Nが50 → O(N⁴)
• Nが20 → O(2^N)かO(N*2^N)
  くらいかなあという感じですね。

参考(ちょっと古いので参考程度に)
[初心者向け] プログラムの計算量を求める方法 - Qiita

計算量のはなし - 赤い黒歴史を蓄積する

終わりに
Rubyで試したら10⁶がギリで10⁶*3くらいでダメでした･･･超えられない速度の壁がありますね。
来週も余裕があれば競技プログラミングのアウトプットをしたいですね、無理そうなら勉強中のGoについて。