オーダー記法（Big-O記法）とは？

オーダー記法（Big-O記法）とは？

March 1, 2026

（かつて別媒体にまとめた記事の再掲です）

優れたアルゴリズムとは？ #

優れたアルゴリズムとは何でしょうか？メモリ消費が少ないアルゴリズムでしょうか？それとも、実装が簡単なアルゴリズムでしょうか？

何をもって優れているかは、目的や状況によって異なりますが、多くの場合において重要視されるのは処理の速度です。

さて、何を持って処理が速いと言えるでしょうか？例えば、以下のアルゴリズムはどちらが速いでしょうか？

function calc1(...args) {}
function calc2(...args) {}

calc1(1, 2); // 1 秒
calc1(1, 2, 0, 5); // 4 秒
calc1(1, 2, 0, 5, 3, 0); // 16 秒

calc2(1, 2); // 4 秒
calc2(1, 2, 0, 5); // 8 秒
calc2(1, 2, 0, 5, 3, 0); // 12 秒

引数が少ないときは calc1 の方が速いですが、引数が多くなるにつれて calc2 の方が速くなっています。

アルゴリズムの性能を評価するために、オーダー記法（Big-O記法）が使用されます。

オーダー記法とは？ #

オーダー記法は、アルゴリズムの性能を表すための表記法です。アルゴリズムの実行時間が、入力サイズに対してどのように増加するかを表現します。（ここでは実行時間を例にしていますが、メモリ消費など他のリソースについても同様に表現できます）

たとえば、O(1)、O(n)、O(n^2)、O(log n) といった書き方をします。

ポイントは「おおまかに」アルゴリズムの性能を表すことです。「おおまかに」とは低次の項を無視して、入力サイズに対して最も影響を与える項だけを考慮することを意味します。

具体例を見てみましょう。

例１：この関数の計算量は？ # 

const numbers = [1, 2, 0, 5, 3, 0];
main(numbers);

function main(numbers) {
  numbers.forEach((n) => {
    numbers.forEach((m) => {
      console.log(n, m);
    });
  });

  numbers.forEach((x) => {
    console.log(x);
  });

  if (numbers.length % 2 === 0) {
    console.log("Length is even.");
  } else {
    console.log("Length is odd.");
  }
}

以下のとおり計算量は x^2 + x + 1 であることが分かります。

function main(numbers) {
  // x^2
  numbers.forEach((n) => {
    numbers.forEach((m) => {
      console.log(n, m);
    });
  });

  // x
  numbers.forEach((x) => {
    console.log(x);
  });

  // 1
  if (numbers.length % 2 === 0) {
    console.log("Length is even.");
  } else {
    console.log("Length is odd.");
  }
}

x^2 + x + 1 をオーダー記法で表すと O(n^2) となります。

最も影響を与える項は x^2 です。それ以外の項は、入力サイズが大きくなるにつれて、全体の計算量に与える影響が小さくなるため、オーダー記法では無視します。

例２：この関数の計算量は？ # 

const numbers = [1, 2, 0, 5, 3, 0];
main(numbers);

function main(numbers) {
  for (let i = 0; i < 4; i++) {
    numbers.forEach((a) => {
      numbers.forEach((b) => {
        numbers.forEach((c) => {
          console.log(a, b, c);
        });
      });
    });
  }

  numbers.forEach((n) => {
    numbers.forEach((m) => {
      console.log(n, m);
    });
  });

  numbers.forEach((x) => {
    console.log(x);
  });

  if (numbers.length % 2 === 0) {
    console.log("Length is even.");
  } else {
    console.log("Length is odd.");
  }
}

以下のとおり計算量は 4x^3 + x^2 + x + 1 であることが分かります。

const numbers = [1, 2, 0, 5, 3, 0];
main(numbers);

function main(numbers) {
  // 4x^3
  for (let i = 0; i < 4; i++) {
    numbers.forEach((a) => {
      numbers.forEach((b) => {
        numbers.forEach((c) => {
          console.log(a, b, c);
        });
      });
    });
  }

  // x^2
  numbers.forEach((n) => {
    numbers.forEach((m) => {
      console.log(n, m);
    });
  });

  // x
  numbers.forEach((x) => {
    console.log(x);
  });

  // 1
  if (numbers.length % 2 === 0) {
    console.log("Length is even.");
  } else {
    console.log("Length is odd.");
  }
}

4x^3 + x^2 + x + 1 をオーダー記法で表すと O(n^3) となります。最も影響を与える項は x^3 であるためです。

参考 #