アルゴリズムの演算性能をざっくりと計算するO記法と計算量の求め方についての前提知識をまとめる。
それぞれ計算時間を記述するものだが、学術的な意味の違いについてまとめる。
アルゴリズムの実行時間を表す3パターンについてまとめる。
多くのアルゴリズムでは、最悪ケースと期待ケースは同じになるようなことが多い。
処理時間が短い順に代表的なものをまとめる。
| O記法 | 計算理論における名称 | 概要 |
|---|---|---|
| O(₁) | 定数時間 | データ量が増加しても処理時間が増加しない |
| O(log n) | 対数時間 | データ量が増えても計算時間がほとんど増えない。増えても計算量の増え幅は小さくなる。 |
| O(n) | 線形時間 | データ量が増加した分だけ処理時間が増える |
| O(n log n) | 準線形、線形対数時間 | O(n)よりやや重い程度 |
| O(n²) | 二乗時間 | 要素から全ての組み合わせペアについて調べるような処理。データ量が増えるほど計算量の増え幅が大きくなる |
| O(n³) | 多項式時間 | 三重ループ |
| O(kⁿ) | 指数時間 | 要素から全ての組み合わせを取得するような処理 |
| O(n!) | 階乗時間 | 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)となる。
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ととなる。
関連書籍