ビッグO記法（ランダウの記号）とは｜アルゴリズム計算量入門

ビッグO記法（ランダウの記号）でアルゴリズムの計算量を図解・例でわかりやすく解説。効率比較や最悪時性能を短時間で理解。

著者: Leandro Alegsa

Big O記法は、アルゴリズムを比較するための方法です。これは、あるアルゴリズムが入力サイズに対してどれだけの時間（実行時間）やどれだけのメモリ（空間）を必要とするかを概念的に表し、アルゴリズム同士を効率の観点で比較できるようにします。実際の実行時間は実装やハードウェアに依存しますが、Big Oは入力サイズが大きくなるときの成長のしかた（漸近的な振る舞い）に着目して評価します。

ビッグオー記法は、問題の複雑さのクラスとしても知られている、問題の複雑さを識別するためによく使用されます。歴史的には数学者のPaul Bachmann (1837–1920)が1896年に著書「Analytische Zahlentheorie」の第2版でこの表記を用い、後にエドマンド・ランドー(1877–1938)が普及させたため、日本語ではしばしばランドーの記号とも呼ばれます。

概念と名前の由来

「Big O」は関数の成長を表す「関数の順序（Order of a function）」に由来し、主に「上界（最悪ケース）」を表現するために使います。つまり、入力サイズ n が十分大きいときに、あるアルゴリズムの実行時間 f(n) が別の関数 g(n) の定数倍以下になる、という関係を示します。これにより、最悪のシナリオでどれだけ時間や資源を消費するかでアルゴリズムを分類できます。

正式な定義（簡潔に）

関数 f(n) と g(n) があり、g(n) が正で単調増加するとき、次が成り立てば「f(n) = O(g(n))」と書きます：ある正の定数 c と n0 が存在して、すべての n ≥ n0 に対して f(n) ≤ c · g(n) が成り立つ。直感的には「f は最終的に g の定数倍より大きくならない」ということです。

よく使われる時間計算量の例

  • O(1) — 定数時間：入力サイズによらず実行時間が一定（例：配列の特定インデックスへの単一アクセス）。
  • O(log n) — 対数時間：二分探索など、入力を毎回半分にするようなアルゴリズム。
  • O(n) — 線形時間：入力を一度ずつ処理するアルゴリズム（例：配列の全要素の合計）。
  • O(n log n) — ほとんどの効率的なソート（例：マージソート、ヒープソート）。
  • O(n^2) — 二重ループなど（例：単純な比較ソートの一部、挿入ソートの最悪ケース）。
  • O(2^n) — 指数時間：再帰的に多数の分岐をする問題（例：冪集合の列挙、ナイーブなフィボナッチ）。
  • O(n!) — 階乗時間：順列をすべて試すような問題（例：巡回セールスマン問題の全列挙）。

注意点・実務的な解釈

  • Big Oは漸近的な挙動を示すため、定数係数や低次の項は無視されます（例：1000n と n は両方 O(n)）。
  • 最悪ケース（worst-case）の記述に使うことが多いですが、平均ケース（average-case）、最良ケース（best-case）も別に表現できます。
  • 時間計算量だけでなく、メモリ使用量（空間計算量）にも同じ記法を用います。
  • 実用上は、入力サイズが小さいときには定数因子や実装の工夫が重要になるため、Big O だけで選択するのは不十分な場合があります。

他の漸近記法

Big O は上界（最悪ケース）を表しますが、他にも漸近表記があります：Θ（シータ）は上界と下界の両方を表す（厳密な漸近的同値）、Ω（オメガ）は下界（最良・下限）を表します。アルゴリズム解析では状況に応じて使い分けます。

実例と直感

たとえば、配列の先頭要素へのアクセスはどんなに配列が大きくなってもほぼ一定時間で行えるため O(1) です。一方、配列内にある値を探す線形探索は最悪で配列全体を調べる必要があるため O(n) です。効率的なソートアルゴリズムは多くの場合 O(n log n) の平均／最悪性能を持ち、単純な二重ループのアルゴリズムは O(n^2) になります。

Big Oは、コンピュータ上でプログラムを実行しなくても、あるアルゴリズムがどれだけ効率的であるかを示す、最悪のシナリオの実行時間を求める式です。これは、コンピュータによってハードウェアが異なるため、プログラムを完成させるのに必要な時間が異なる場合にも有用です。Big Oは常に最悪のケースを想定しているので、速度の一貫した測定値を示すことができます：ハードウェアに関係なく、O ( 1 ) {\displaystyle O(1{\displaystyle O(1)})}は常にO ( n ! ) {\displaystyle O(n!)}{\displaystyle O(n!)}よりも速く完了するようになっています。

まとめ（実務へのアドバイス）

  • アルゴリズム選択ではまず漸近時間・空間計算量で大まかに評価する。大きな入力サイズが想定される場合、対数や線形に近い成長を持つ手法を優先する。
  • 小さな定数因子や実装の工夫も無視できないため、プロトタイプやベンチマークで実際の性能を確認すること。
  • 平均ケースと最悪ケースの違いを理解し、用途に応じて適切な解析（平均・最悪・空間）を行う。

例としては、以下のようなものがあります。

以下の例はすべて Python で書かれたコードを使用しています。これは Big O 型の完全なリストではないことに注意してください。

定数

O ( 1{\displaystyle O(1)}) {displaystyle O(1)} .入力に関係なく、常に同じ時間がかかる。例えば、整数（xと呼ばれる）を受け取って、その値の２倍の値を返す関数を考える。

def double(x): return x * 2 #xの値を2倍した値を返す

この関数は、入力を受け付けた後、必ず１ステップで出力を返す。常に同じ時間がかかるので定数なので、O ( 1 ) {\displaystyle O(1)} .{\displaystyle O(1)}

リニア

O ( n ) {displaystyle O(n)} .{\displaystyle O(n)}n {displaystyle n}nで表される入力の大きさに応じて増加する。ある関数がnを受け入れて、1からnまでのすべての数を返すとしよう。

def count(n): i = 1 #値が1の"i"というカウンタを作成します while i <= n.#iがn以下の場合 print(i) #iの値を表示する i = i + 1 #iを"i + 1の値"と再定義する

5の値を入力すると、1, 2, 3, 4, 5 {\displaystyle 1,2,3,4,5}が出力されます。{\displaystyle 1,2,3,4,5}を出力します。同様に、100と入力すると、1,2,3...98,99,100 {\displaystyle 1,2,3...98,99,100}と出力され{\displaystyle 1,2,3...98,99,100}、100ループを完了する必要がある。入力がn {\displaystyle n}nならば、アルゴリズムの実行時間は毎回正確にn {\displaystyle n}nループするので、O ( n ) {\displaystyle O(n)} .{\displaystyle O(n)}

要因

O ( n ! ) {displaystyle O(n ! ) } .{\displaystyle O(n!)}乗的に増加し、入力に伴って時間が大幅に増加することを意味する。例えば、世界の5つの都市を訪問して、可能な限りの順序（順列）を見たいとします。Pythonのitertoolsライブラリを使って書けるアルゴリズムは以下の通りです。

import itertools #import the itertools library cities = ['London', 'Paris', 'Berlin', 'Amsterdam', 'Rome'] #選ばれた都市の配列 def permutations(cities).permutations(cities): #入力として都市の配列を取る: for i in itertools.permutations(cities): #項目の各並べ替えについて (変数 "i" に代入) print(i) #出力 i

このアルゴリズムは、各都市のユニークな順列を計算して出力します。出力の例としては、以下のようなものがあります。

('London', 'Paris', 'Berlin', 'Amsterdam', 'Rome', 'Amsterdam') ('London', 'Paris', 'Amsterdam', 'Berlin', 'Rome', 'Amsterdam') ...('Rome', 'Amsterdam', 'Paris', 'Berlin', 'London') ('Rome', 'Amsterdam', 'Berlin', 'London', 'Paris') ('Rome', 'Amsterdam', 'Berlin', 'Paris', 'London')

ここでは、入力リストは5つの項目で、選択するごとに残りの選択肢が1ずつ減っていく。 つまり、5つの入力は、5×4×3×2×1 {\displaystyle 5 4times 4Times 3\times 2Times 1{\displaystyle 5!}}の{\displaystyle 5\times 4\times 3\times 2\times 1}項目を選択する（または、5 !入力がn {displaystyle n} nCities longならば、出力数はn !つまり、{\displaystyle n!}すべての順列を通るとすると、それを完成させるには、O ( n ! ) {\displaystyle O(n ! ) }の{\displaystyle O(n!)}ループが必要になる。

リトルオー記法

Big Oのより厳格なバージョンがlittle-oである。big Oとlittle-oの違いは、little-oが厳密な上限であることである。O ( n ) {\displaystyle O(n)}{\displaystyle O(n)}が入力サイズに基づいて完了時間がこの最大値まで増加することを意味するのに対し、o ( n ) {\displaystyle o(n)}は完了時間が一般的にこの時間以下になることを{\displaystyle o(n)}意味する。言い換えれば、Big Oはすべてのループが最も長いパスを取り、プロセスが可能な限り長くかかると仮定するのに対し、little-oは実際の実行時間についてより現実的である。ループの数が6面のサイコロを振ることに基づいている場合、Big Oは常に6が振られると仮定するのに対し、little-oは他の数字が振られる確率が等しいことを考慮する。

質問と回答

Q:ビッグ・オー表記とは何ですか?


A:ビッグ・オー表記法とは、異なる関数の成長率を比較する方法で、多くの場合、完了までにかかるメモリと時間を計算することで、異なるアルゴリズムの効率性を比較するために使用されます。また、問題がどの程度複雑かを識別するためにも使われます。

Q:この表記法を最初に使ったのは誰ですか?


A:数学者のPaul Bachmann（1837-1920）が1896年に出版した「Analytische Zahlentheorie」でこの表記法を初めて使用しました。

Q:ビッグ・オーとは何の略か?


A:ビッグ・オーは "order of the function "の略で、関数の成長率を意味する。

Q:ビッグ・オーはどのように使われるのですか?


A:ビッグ・オー表記は、関数の成長率の上限（可能な限り高い値）を求めるために使われます。つまり、入力を出力に変えるのにかかる最長時間を算出するのです。つまり、アルゴリズムは、毎回最長経路をとることになる最悪のケースでどれだけの時間がかかるかでグループ分けすることができるのです。

Q:ランドーシンボルとは何ですか?


A:ランドー記号とは、ビッグ・オー表記法のことで、この表記法を普及させたエドモンド・ランドー（1877-1938）にちなんで命名されました。

Q:なぜBig Oが有用なのですか?



A:ビッグ・オーは、常に最悪のケースを想定しているため、コンピュータ間のハードウェアの違いに関係なく一貫性があり、コンピュータ上でプログラムを実行しなくても速度を測定することが可能です。また、実際にコンピュータで実行しなくても、アルゴリズムがどの程度効率的であるかを示すことができます。


百科事典を検索する
AlegsaOnline.com - 2020 / 2025 - License CC3