Big O Notation

アルゴリズムの「燃費」の話。データが増えたとき、どれくらい遅くなるか？

Common Orders

  • O(1) Constant: 最強。データが1億件になっても一瞬。
  • O(n) Linear: データ量と比例して遅くなる。全件ループなど。
  • O(n²) Quadratic: 激遅。二重ループ。データが増えると爆発的に遅くなる。

Code Examples

big-o.js
// O(1) - Constant
const first = (arr) => arr[0];


// O(n) - Linear
const find = (arr, target) => {
  for (let item of arr) {
    if (item === target) return true;
  }
  return false;
};


// O(n^2) - Quadratic (Nested Loop)
const match = (arr) => {
  for (let i of arr) {
    for (let j of arr) {
      console.log(i, j);
    }
  }
};