競技プログラミングには実行時間が決められています。この実行時間をオーバーすると正解できません。そこで、今自分が書いてるプログラムが一体どのような速度で動作するのかを考えながら書かなければいけません。このファイルでは実行時間について考えます。
実行時間を考えるのに大切なのは、計算量という考え方です。計算量は一般に、O記法(オー記法、もしくはビッグオー記法と呼ぶ)を使って表します。O記法では計算量を、O(n) や O(n^2) のような形で記述します。
#計算量の求め方
n = 10
count = 0
#---------------------------------------------------
#ここから下の計算量を求める
for i in range(10):
count += 1 #n回実行
for i in range(10):
for j in range(10):
count += 1 #n^2回実行
count += 1 #1回実行
print(count) #1回実行
上のコードの計算量を求めてみましょう。
①プログラムの計算や代入をする行の実行する回数を求めます。上のプログラムではコメントで書いてあります。
②もとめた各数を足し算する式を書きます。
上の例では、n + n^2 + 1 + 1 になります。
③必要ない物を省く
・最大次数以外の項
・係数
これらを省いた結果は n^2になります。
この結果、上のプログラムはO(n^2)であることがわかりました。
上記の方法でプログラムの計算量を求めることができます。この下は計算量の例を書いていきます。
#O(1)のプログラム
a = 1 + 1
print(f'O(1)の結果:{a}')
#--------------------------------
#O(n)のプログラム
n = 100
count = 0
for i in range(n):
count += 1
print(f'O(n)の結果:{count}')
#--------------------------------
#O(n)のプログラム
n = 100
count = 0
for i in range(n//2):
count += 1
print(f'O(n)の結果:{count}')
#--------------------------------
#O(n^2)のプログラム
n = 100
count = 0
for i in range(n):
for j in range(n):
count += 1
print(f'O(n^2)の結果:{count}')
#--------------------------------
#O(log(n))のプログラム
n = 100
count = 0
while count * count < n:
count += 1
print(f'O(log(n))の結果:{count}')
ビッグオー記法は定数倍の違いは無視するので数倍程度の計算結果の違いはありますが、基本的な実行時間はO(n^2) > O(nlog(n)) > O(n) > O(log(n)) > O(1)になります。
これ以外にもO(2^n)やO(n!)などのプログラムが想定解の場合があります。しかしこの場合、計算量はnの増加に伴い急激に増大するのでO(2^n)ではnは20、O(n!)ではnは10が最大でしょう。それよりも大きいnが想定される場合は実行時間内にプログラムが動作しません。
邪道かもしれませんが、与えられた制約条件から予想される計算量を考えることができ、プログラムの設計に生かすことができます。
n < 10^9 → 二分探索、一発でぱしっと答えを出す
n < 10^5 → 線形探索、ソート、累積和、幅優先探索
n < 1000 → O(n^2)でなんかやる。
n < 100 → O(n^3)でなんかやる。
n < 20 → O(2^n)例えば、n枚のコインの向きを全部試す(ビット全探索)
ぱっと思いついたのでこんなもんなんですけど、C問題以降は計算量に気を付けて解けるといいと思います。