アルゴリズム｜計算量

最近AtCoderを始めたので、計算量と実行時間についての備忘録です。
サンプルのコードはC#で書いています。

オーダー記法

このような式の計算量をオーダー記法で表現するとO(N²)となります。

3N²＋3N＋3  

下記の手順で計算量を求めます。

1. まず係数を省略する。 -> N²＋N＋3
2. 定数を1に変換する。 -> N²＋N＋1
3. Nを大きくしたときに一番影響が大きい項を取り出して、O(項)とする。 -> O(N²)

一番影響が大きい項に注目するという点がポイントです。

O(N)

for文でN回ループをまわすと計算量はO(N)となります。

for (int i = 0; i < N; i++) {
  // 何らかの処理
}

O(N²)

for文でN回の二重ループをまわすと計算量はO(N²)となります。

for (int i = 0; i < N; i++) {
  for (int j = 0; j < N; j++) {
    // 何らかの処理
  }
}

O(logN)

logxN = Mは「xをM乗したらNになる」という意味です。
二分探索のように、半分にしていく処理をN回繰り返すと計算量はO(logN)となります。
下記のコードは、ソートされた数字の配列の中から、numより大きい最初の値を二分探索で見つけて、その値のインデックスを返す関数です。

public static int BinarySearch(int[] array, int num)
{
  int start = 0;
  int last = array.Length;
  int mid;

  while (start < last)
  {
    mid = start + (last - start - 1) / 2;
    if (array[mid] > num)
    {
      last = mid;
    }
    else
    {
      start = mid + 1;
    }
  }

  return last;
}

実行時間

おおよその実行時間は下表の通りです。
引用元: W - 2.06.計算量

N	O(logN)	O(N)	O(N²)
1	一瞬	一瞬	一瞬
10	一瞬	一瞬	一瞬
1000	一瞬	一瞬	0.01秒くらい
10⁶	一瞬	0.01秒くらい	3時間くらい
10⁸	一瞬	1秒くらい	3年くらい

AtCoderの問題の実行時間制限は2秒であることが多いので、そういった問題を解く時は「1秒で処理できるfor文のループ回数は10⁸回くらい」と覚えておくと良さそうです。