概要

アルゴリズムの演算性能をざっくりと計算するO記法と計算量の求め方についての前提知識をまとめる。

計算量（オーダー）とは

• アルゴリズムの演算性能をデータ量の増加に対し、実行時間がどれくらい増加するかの割合で表した指標。
  • 時間計算量
    • 処理時間
  • 空間計算量
    • メモリ使用量

Big O/Big θ/Big Ω

それぞれ計算時間を記述するものだが、学術的な意味の違いについてまとめる。

• Big O
  • 計算時間の上限
• Big θ
  • 計算時間の下限
• Big Ω
  • OとΩの両方

最善/最悪/期待ケース

アルゴリズムの実行時間を表す3パターンについてまとめる。

• 最善（best）ケース
  • 計算量の下限。すべての要素の値が等しいケース。最悪ケースや期待ケースと値が大きくかけ離れ、大抵はO(₁)で実行できてしまうようなケースになるため、あまり議論されない。
• 最悪（worst）ケース
  • 計算量の上限。
• 期待 （average）ケース
  • 計算量の平均。要素の値が平均的なケース。

多くのアルゴリズムでは、最悪ケースと期待ケースは同じになるようなことが多い。　

O（オーダー）記法

処理時間が短い順に代表的なものをまとめる。

計算量の求め方

ステップ数を計算して、その合計を元に計算量を求める。 計算量を求める際に、以下の二点は重要度が低いため、省略する。

• 最大次数項以外を省略する
  • O(n²+n)
    • O(n²)とする
• 係数を省略する
  • O(2n)
    • O(n)とする

ステップの計算で処理の実行時間を足すか掛けるかは、それぞれの処理が同時に起きるか、起きないかで考える。

同時に起きない場合は実行時間を足すケース。

for (condition) {
  // do something
}

for (condition) {
  // do something
}

同時に起きる場合は、実行時間を掛けるケース。

for (condition) {
  for (condition) {
    // do something
  }
}

例

リニアサーチ

const targetData = 4; // 1回実行
const data = [1, 2, 3, 4, 5]; // 1回実行

for (let i = 0; i < data.length; i++) {
	if (targetData == data[i]) {
  	console.log(`${i}番目でデータを発見した`); // data.length回実行される→n回実行
    return;
  }
}

console.log('目的のデータはない'); // 1回実行

上記のコードの場合、ステップ数の合計は1+1+n+1=3nとなる。 係数は除くので、計算量はO(n)となる。

for文の二重構造

const data = [1, 2, 3, 4, 5]; // 1回実行

for (let i = 0; i < data.length; i++) {
	console.log(`${i}回目の処理`); // 1回実行される
	for (let j = 0; j < data.length; j++) {
		console.log(j); // 4 * 4 回実行される→n²回実行
  }
}

上記の場合は、1+1+n²=2n²のステップ数となるので、計算量は係数を除き、O(n²)となる。

計算量が対数を取るようなアルゴリズム

const n = 10;  // 1回実行される

for (let i = 0; i < n; i = i * 2) {
  console.log(i++); // log2ⁿ回実行される
}

nが1の時 ループ回数 1

nが4の時 ループ回数 2

nが8の時 ループ回数 3

ループ回数はlog2ⁿで求められる。 1+log2ⁿのステップ数となるので、諸々を省略して計算量はlog nととなる。

参考リンク

• 計算量オーダーについて
• [初心者向け] プログラムの計算量を求める方法
• [初心者向け] プログラムの計算量を求める方法
• 計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜
• techscore - 開発新卒に捧ぐ、基本のアルゴリズムと計算量

参考書籍

• 世界で闘うプログラミング力を鍛える本 コーディング面接189問とその解法
  • O記法についての話が例題もあってわかりやすい。
• アルゴリズム図鑑 絵で見てわかる26のアルゴリズム
• プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
• アルゴリズムを、はじめよう
• Web+DB press vol.91 2016