競技プログラミング Edit

【競プロ】計算量オーダーの考え方

競技プログラミングの解説では計算量オーダーという言葉が出てきます。

私も競技プログラミングを始める前はプログラムの計算量を考えるときは「なんかレスポンスが遅いから効率化してみよう」程度の感覚でプログラムを書いていました。

個人で書くプログラムに厳密な制限時間はなく「使ってみた感覚で早いか、遅いか」しか気にしていなかったからです。

しかし、競技プログラミングでは厳密に実行時間が制限されているので制限時間を少しでもオーバーしてしまうとTLEになってしまうので計算量オーダーの考え方を知っておく必要があります。

計算量

プログラムを実行するのに必要な時間の目安を表します。

(競技プログラミングで)プログラムの実行時間を考えるときのポイントは次の2つです。

- プログラムの計算量
- 入力値の量

競技プログラミングでは最大入力量に対して、計算量を考え実行時間制限に間に合うかということを考えていきます。

計算量オーダー

必要になる時期

計算量オーダーに関しては、ABCのC問題を解くレベル、緑色にになってから覚えれば大丈夫です。

D問題以上を解く場合には必須になるので少しずつ覚えていきましょう。

-競技プログラミング, Edit