コースが扱った内容とスキップした内容
ハミングのコースは、アナログ-デジタル変換、エラー訂正、シミュレーション、統計、数値解析、n次元幾何学を扱いました。彼は計算的に考えていました — 信号処理、符号理論、デジタルフィルタリングはすべて計算的推論を必要とします。
彼はアルゴリズムの計算量を体系的に教えませんでした。
なぜギャップが存在したのか
ハミングのメンタルモデルは、ハードウェアのボトルネックが支配的だった時代に形成された。問題は「1チップあたり何個のトランジスタか？」だった。アルゴリズムは利用可能なハードウェア上で実行された。N=100の場合、O(N²)アルゴリズムは10,000回の演算を必要とする。N=1,000の場合、1,000,000回。N=10,000（今日では依存グラフ、ソーシャルネットワーク、パッケージマネージャで日常的）：100,000,000回。O(N)とO(N²)の違いは、ハミングが扱っていた規模では見えにくかったが、彼の学生たちが生きる規模では壊滅的だった。
ドナルド・クヌースは1968年からThe Art of Computer Programmingを出版し始めた——ハミングが研究活動の最盛期だったのと同じ年だ。Big O記法は1970年代から1980年代にかけて標準的なアルゴリズム用語となった。ハミングの講義は1995年に行われたが、彼の計算に関するメンタルモデルはそれより早く形成されていた。彼はこの章を更新することはなかった。
ハミング自身の基準による根本原理
ハミングの根本原理のテスト：(1) 長期間にわたって存続していること、(2) 残りの分野が標準的な手法でそこから導き出せること。
Big Oは両方のテストに合格する。成長率解析はクヌース以来存続している。それからアルゴリズム選択、データ構造の選択、パフォーマンス予測を導き出せる——実用的なコンピュータサイエンスのほとんどは、「コストはNの増加に伴ってどのように増大するか？」という問いから流れ出している。ハミングは自らの分野で最も耐久性のある根本原理を見逃した。
根本原理としてのBig O
ハミングは、根本原理は特定の技術よりも長く存続すると教えた。彼は微積分を例に挙げた：一度発明されれば、物理学、工学、経済学、生物学にわたって何世紀にもわたって適用可能である。周辺的なツールは現れては消えるが、根本原理は複利的に蓄積される。
コストの成長の仕方
Big Oは、入力が増えるにつれてコストがどのように成長するかを測る。定数係数ではなく、成長率だ。N=100でどちらも「数ミリ秒」で動作する2つのアルゴリズムでも、一方がO(N)、他方がO(N²)なら、N=10,000では10,000倍の差が生じる可能性がある。
一般的な計算量クラス
O(1) — 定数時間。 Nに関係なくコストは一定。例：キーを用いたハッシュテーブルの探索、インデックスによる配列アクセス、スタックのpush/pop。Nを2倍にしても何も変わらない。
O(log N) — 対数時間。 各ステップで残りの作業量が半分になる。例: ソート済み配列での二分探索、ゲームエンジンでのBVH空間クエリ、平衡二分木の操作。N=1,000,000の場合: log₂(1,000,000) ≈ 20ステップ。
O(N) — 線形時間。 コストは入力サイズに比例して増加する。例: リストの線形走査、ファイルの読み込み、コレクション内の要素数カウント。N=10,000の場合: 10,000回の操作。
O(N log N) — 線形対数時間。 ほぼ線形だがわずかに悪い。例: マージソート、ヒープを用いた効率的な最短経路アルゴリズム（Dijkstra法）。N=10,000の場合: 約133,000回の操作。
O(N²) — 2乗時間。 コストが爆発的に増加する。例: 同じリストをループしながらlist.contains()を呼び出す、バブルソート、素朴な全ペア比較。N=1,000の場合: 1,000,000回の操作。N=10,000の場合: 100,000,000回の操作。
O(2^N) — 指数関数. 実用的な規模では使用不可能。例: 総当たり組み合わせ、すべての部分集合の探索。N=30 では 10億回以上の演算が必要。
視認できる規模
N=10 回の比較:
O(N): 10
O(N²): 100
比率: 10x
N=1,000 回の比較:
O(N): 1,000
O(N²): 1,000,000
比率: 1,000x
N=10,000 回の比較:
O(N): 10,000
O(N²): 100,000,000
ratio: 10,000xN=10では差はほとんど目立ちません。N=10,000では、O(N²)のアルゴリズムはO(N)の10,000倍遅く実行されます。これが、MOAD-0001が何十年もの間気づかれなかった理由です。1993年に実行されたグラフには50個のノードしかありませんでした。2020年までに、同じコードは50,000個のノードを持つ依存関係グラフで実行されました。
3つの操作を分類する
複雑度クラスを具体的な操作に適用します。各操作の重要な質問は、Nが増えるにつれて何回の操作が必要かということです。
正しいコード、誤った成長曲線
O(N²) 時間で動作する正しいコードは、O(N) コードと同一の結果を生成する。テストは通る。出力は一致する。例外は発生しない。欠陥は成長曲線の中に隠れている。
この特性により、O(N²) の欠陥は堆積性を持つ：それらは動作するコードの中に石灰化し、N が閾値を超えたときにのみ可視化される。コードは変更されていない。周囲の世界が変化したのだ。
MOAD-0001: 堆積的欠陥
最も一般的な例: グラフ探索ループ内の visited = []。
visited = []
for node in graph:
if node not in visited: # 呼び出しごとに O(N) の走査
visited.append(node)
process(node)各 not in visited の呼び出しは 0 から len(visited)-1 までの要素を走査します。N 回の呼び出し × 平均 N/2 回の走査 = 合計 O(N²)。修正は 1 行です。
visited = set() # O(1) のメンバーシップテスト
for node in graph:
if node not in visited: # O(1) のハッシュルックアップ
visited.add(node)
process(node)同じ動作。同じ出力。同じテストが通る。成長率が O(N²) から O(N) に変わる。N=1,000 では 1,000 倍高速。N=10,000 では 10,000 倍高速。
なぜハミングの時代がこれを植え付けたのか
初期の Java と C では、ArrayList（動的配列）が標準的なシーケンシャルコンテナでした。Set は存在していましたが慣用的に使われていませんでした。開発者は馴染みのあるものを使いました。1993 年に N=50 のグラフ探索を visited = [] で行うとマイクロ秒単位で完了しました。そのコードはバージョン管理に入り、コピーされ、ライブラリにラップされ、パッケージマネージャーで配布されました。2020 年には同じパターンが 50,000 ノードの依存グラフで実行されました。
そのコードは 1993 年には正しかったです。周囲の世界が変わったときに高コストになりました。ハミングの時代は成長率の問題に名前を付けなかったことで、この種の欠陥を植え付けました。
診断と修正
診断を適用する：O(N²) のパターンを見つけ、修正を特定する。
どのような命名変更が必要か
Big O に名前が付く前、プログラマーは「これは遅い」と気づいていました。彼らはプロファイリングを行い、書き換えを行いました。しかし、そのパターンを教えることはできませんでした — 個別の事例を指し示すことしかできなかったのです。名前を持たないパターンは伝播できません。
Big O に名前が付いた後、シニアエンジニアは「これは O(N²) なので、セットに置き換えましょう」と言うことができ、ジュニアエンジニアはそのパターンを理解し、適用し、さらに教えることができました。名前によってパターンは知識の移転可能な単位になりました。
Hamming は他の分野でもこのダイナミクスを理解していました。彼は 1960 年代に「スパゲッティコード」という名前を付けることで、誰もが経験していたが誰も名前を付けていなかった欠陥のクラスを、コミュニティが認識し、議論し、最終的に根絶することを可能にしたと説明しました。同じメカニズムが計算量クラスにも当てはまります。
Unhamming は Hamming が省略した語彙を追加します：O(1)、O(log N)、O(N)、O(N log N)、O(N²)、O(2^N)。これらの名前により、読んだコードの中で成長曲線を見ることができ、スケール時のパフォーマンスを予測し、修正を正確に伝えることができます。これらは Hamming 自身が基本的なものに求めた条件 — 持続可能で、分野の大部分を生み出す — を満たしています。 [TITLE who_coined_big_o/]
数論からコンピュータサイエンスへ
Big O 記法はコンピュータサイエンスで生まれたものではありません。純粋数学、特に数論において、Donald Knuth がアルゴリズム用に採用する 74 年前にすでに存在していました。
Paul Bachmann, 1894
ドイツの数学者 Paul Bachmann は、1894 年の著書『Die Analytische Zahlentheorie』（解析数論）の中で O 記法を導入しました。彼は、ある量が別の量を定数倍の範囲で超えないことを簡潔に表現する方法を必要としていました。『f(n) = O(g(n))』と書くことで、f は g と同じかそれより遅い速度でしか増加しないことを示しました。これにより、数論学者は近似の誤差項を扱う際に、正確な定数を追跡せずに議論できるようになりました。
Bachmann はループやデータ構造、実行時間を考えていたわけではありません。彼が考えていたのは素数の分布、特に素数定理における誤差項についてでした。
Edmund Landau, 1909
もう一人のドイツ人数学者 Edmund Landau は、1909 年の著書『Handbuch der Lehre von der Verteilung der Primzahlen』（素数の分布に関するハンドブック）でこの記法を普及させました。Landau は関連する o（リトルオー）記法も導入し、漸近記号のファミリーを非常に頻繁に使用したため、この記号群は Bachmann-Landau notation または単に Landau notation と呼ばれるようになりました。
60 年間、O 記法は完全に数学の世界に留まり、プログラマがこれを考えることはありませんでした。
Donald Knuth, 1968 & 1976
Donald Knuthは記法をコンピュータサイエンスに翻訳しました。『コンピュータ・プログラミングの技法』（第1巻、1968年）の中で、KnuthはO記法を使ってアルゴリズムの実行時間を記述しました。これはBachmannの道具を新しい分野に直接移植したものです。彼はアルゴリズム解析にO記法を体系的に適用した最初の人物でした。
1976年、Knuthは『SIGACT News』に「Big Omicron and Big Omega and Big Theta」という短い論文を発表しました。彼は下界を表すOmega（Ω）と、厳密な境界を表すTheta（Θ）を導入し、今日のコンピュータサイエンスで使われる3つの記号の語彙を完成させました。また、これらの記号の使用を分野全体で標準化することを主張しました。これは意図的な標準化の行為であり、採用を加速させました。
1980年代初頭までに、Big Oはすべてのアルゴリズム教科書に登場するようになりました。1990年代には、面接の標準語彙となりました。
74年の旅路
1894年 — Bachmannが数論でOを導入
1909年 — LandauがO、oおよび完全な記法ファミリーを普及させた
1953 — ハミングがBell Labsで研究を開始（Big OをCSツールとして学ぶことはなかった）
1968 — クヌースがTAOCP第1巻でOをアルゴリズム解析に適用
1976 — クヌースがΩとΘを追加し、標準化を主張
1980年代 — Big OがすべてのCSカリキュラムに導入される
1993 — MOAD-0001堆積層が本番コードに形成される
1995 — ハミングが最終版の講義を実施；Big Oは扱われなかった
2026 — MOAD-0001が1,000以上のオープンソースプロジェクトで発見されるBachmannのツールは74年間、純粋数学の領域に留まり、すべての数学者には見えていたが、すべてのプログラマーには見えていなかった。Knuthはその移植を見抜いた。Hammingは同じ時代に、同じコンピューティングコミュニティと協力しながらも、それを自らのコースに取り入れることはなかった。
Why Knuth's Standardization Mattered
Knuthの1976年の論文は、OmegaとThetaの導入を超えたことを成し遂げた。そこでは、分野に一貫した表記が必要であり、一貫性のない表記が実際に有害であると主張された。異なる教科書ではOが異なる意味で使われていた——上界を表す場合もあれば、近似を表す場合もあり、定数が重要かどうかを明示しない場合もあった。Knuthはこれを整理した。
これは、Hammingのパターン命名のダイナミクスを表記そのものに適用したものだ。Knuthが記号を標準化する前は、エンジニアは教科書、論文、チーム間で複雑さの主張を正確に伝えることができなかった。標準化後は、「これはO(N log N)で動作する」という表現が、誰が言おうと完全に一つの意味を持つようになった。
Knuthはまた、非公式な翻訳も提供した。「O(f(n))とは、十分に大きいすべてのnに対して、実行時間がf(n)の定数倍以内に収まることを意味する。」この解釈——上界、定数倍まで、大きな入力に対して——は、すべてのプログラマーが学ぶ標準的な直観となった。