計算量の考え方

計算量の評価方法に関して

競技プログラミングなどに参加する上で，後々問題になってくるのが計算量に関する考え方です．
計算量には

• 時間計算量
• 領域計算量

のふたつがあります．
実際にシステムにアルゴリズムを適用させる際にはこの二つの制約を守ったり，出来るだけ計算量を小さくする必要があります．

O表記に関して

アルゴリズムの計算量を評価するもののひとつがO表記です．
例えば，プログラム上でforループが一つあればn回ループを処理することになるのでO(n)となります．
ここでO(n)とO(n²)を比較してみましょう.
nが最大100までの場合
O(n)のプログラムは最大で100回ループを処理する
一方で，
O(n²)のプログラムは最大で10000回ループを処理する
この二つを比較では計算量は100倍に増えています．
つまり，nの数に比例して計算量は多くなり，発散してしまいます．
また，オーダーの中身の値，つまり，ループの回数にも大きく依存して計算量は増えていきます.

計算量の比較

nの値に応じてそれぞれのオーダーがどのように変わるか表にまとめたので参考までに覚えておくと役にたつと思います．
表からわかるようにオーダーが大きければnの値が小さかったとしても計算量はとても大きくなってしまいます．
実際に，競技プログラミングに参加する際には時間制約が2秒というように指定されていたりします.
なるべくオーダーは小さくなるようにアルゴリズムを構築しましょう！