コード構造が複雑性をどのように明かすか

コードからビッグオーを特定する方法

ビッグオーはコードの形に隠れています。4つのパターンがほとんどのケースをカバーします：

N個の項目上の単一ループ：O(N)

# O(N)：リストの1回の走査
for item in list_of_n_items:
    process(item)

N個の項目上のネストされたループ：O(N²)

# O(N²)：すべての項目がすべての他の項目とペアになります
for item_a in list_of_n_items:
    for item_b in list_of_n_items:
        compare(item_a, item_b)

定時間検索：O(1)

配列インデックスアクセス、ハッシュテーブル検索—サイズに関わらず1ステップ。

分割統治（各ステップで問題を半分に分割）：O(log N)

二分探索：各チェックで残りの項目が半分になります。

---

隠れたO(N²)：ループ内のリスト

# これはO(N)のように見えますが、実際にはO(N²)です
visited = []
for item in list_of_n_items:
    if item not in visited:   # visitedのすべてをスキャン：O(N)
        visited.append(item)  # 全体のループ：O(N²)

if item not in visited行は、各反復でvisitedのすべての要素をスキャンします。リストスキャンにはO(N)かかります。N回実行されるループが、各実行でO(N)の作業を行う：O(N) × O(N) = O(N²)。

このパターンは1,000以上のオープンソースプロジェクトに現れます。修正は1文字で済みます：visited = []をvisited = set()に置き換えます。セットメンバーシップテストはO(1)で、O(N)ではありません。1つの変更です。同じ結果。N=1,000で1,000倍高速。

このコードを分類して修正する

このコードを読んでください：

result = []
for name in student_names:
    if name not in result:
        result.append(name)

理論と実践が出会う

野生のビッグオー

ビッグオーは単なる理論ではありません。同じタスクで、数秒で完了するプログラムと17分かかるプログラムを分けます。

実際の例：ビルドシステムの依存関係サイクル検出。

ソフトウェアをインストールするとき、コンピュータは依存関係のグラフを解決します：パッケージAはB が必要、BはCが必要、など。ビルドシステムはこのグラフをサイクルについてチェックします。

O(N²)サイクル検出アルゴリズムはN=100パッケージで正常に動作します。N=50,000パッケージ（実際のプロジェクト）で：17分かかります。O(N)修正：10秒。

この正確な欠陥はGHC（Haskellコンパイラ）、pip（Pythonパッケージマネージャー）、Maven（Javaビルドシステム）、Cargo（Rustパッケージマネージャー）、&1,000以上の他のプロジェクトに存在します。

作者が無注意だからではありません。N が小さい時にvisited = []が書かれました。コードが石化しました。Nが成長しました。ビルドが半時間かかるまで誰も気づきませんでした。

ビッグオーは、何が起こったかを名前を付け、修正できる語彙です。

---

もっと深く学びたいですか？ unhammmingコースはビッグオーの完全な章、MOAD-0001（1,000以上のオープンソースプロジェクトで見つかった実際のO(N²)欠陥）、&パターンに名前を付けることがどこでもそれを見つけることができる理由が含まれています。失われた章：アルゴリズム複雑度を参照してください。

ビルド時間を予測する

ビルドシステムはO(N²)サイクル検出を使用しています。

測定されたビルド時間：

- N=100パッケージ：0.01秒

- N=1,000パッケージ：1秒

O(N²)の場合：時間は(N_new / N_old)²としてスケーリングします。

O(N)の場合：時間は(N_new / N_old)としてスケーリングします。