時間内に完了するアルゴリズム：計算量の確認

関数を書いて、テストデータで実行すると問題なく動作します。本番データに入ると、500行ではなく500,000行になり、リクエストがタイムアウトします。これは常に起こり、ほぼいつも小規模で妥当に見えるコードの背後に隠れた計算量の問題です。

なぜあなたのラップトップはうそをついたのか

O(n²) アルゴリズムが100個の項目に対して実行される場合、10,000 回の操作を実行します。これはどのマシンでも即座に実行できます。同じアルゴリズムを 100,000 個の項目に対して実行すると、100 億の操作になります。ミリ秒ではなく、数分から数時間かかります。n から n² へのジャンプは、n が大きくなるまで危険に感じず、それが正確にコードレビューとローカルテストをすり抜ける理由です。

古典的な例：ネストされたループで重複をチェックする。

def has_duplicates(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

これは O(n²) です。set に置き換えます：

def has_duplicates(items):
    seen = set()
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False

これで O(n) になります。set のルックアップは平均 O(1) なので、関数全体は二次ではなく線形にスケーリングします。10,000 個の項目では、約 1 億回の比較と 10,000 回の比較の違いになります。

最適化する前に測定する

推測しないでください。マイクロベンチマークには timeit を使用します：

import timeit
timeit.timeit(lambda: has_duplicates(list(range(5000))), number=10)

より大きな関数については、cProfile でプロファイリングします：

python -m cProfile -s cumulative myscript.py

cumtime 列を確認します。1 つの関数が実行時間の 90% を使用する場合、それがターゲットです。ボトルネックではないコードの最適化は時間の無駄であり、利益のない複雑性を追加します。

静かに遅くなる一般的なパターン

リスト メンバーシップの繰り返しチェック。 if x in my_list はリストに対しては O(n) ですが、set または dict に対しては平均 O(1) です。ループ内のメンバーシップをチェックしている場合、O(n) ループ内の O(n) チェックは全体で O(n²) になります。リストを set に置き換えて、O(n) に戻します。

ループ内の文字列連結。 Python では、文字列のループ内の result += chunk は、文字列が不変であり、各連結が全体をコピーするため、最悪の場合 O(n²) です。代わりに ''.join(chunks) を使用します。文字列を一度構築します。

必要ないのにソートしている。 sorted() は O(n log n) です。ループ内で呼び出して各イテレーションの最大または最小を見つけるだけの場合は、max()/min() (O(n)) を使用するか、k が小さい場合は繰り返しの極値が必要な場合は heap (heapq) を使用するのが良いでしょう。heapq.nlargest(k, data) は O(n log k) であり、k が小さい場合、リスト全体をソートするよりもはるかに安いです。

メモ化のない再帰関数。 素朴な再帰 Fibonacci は O(2ⁿ) です。同じ部分問題を繰り返し計算するためです。functools.lru_cache を追加すると、O(n) に低下します：

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

実際のコードから Big O を素早く読む

同じ入力をループネストしているかどうかをカウントします。これは通常、指数です。単一ループは O(n) です。ループ内のループは、内部ループの範囲が縮まらない限り O(n²) です（バブルソートの最適化された形式のように、最悪の場合でも O(n²) ですが、比較は少なくなります）。問題を半分に分割する再帰呼び出し（二分探索やマージソートなど）は、O(log n) または O(n log n) をポイントします。レベルごとに複数の呼び出しに分岐する再帰呼び出し（素朴な Fibonacci など）は指数時間をポイントします。メモ化または反復的な書き直しが必要であることを示す強い信号です。

良い習慣：ネストされたループまたは再帰をユーザーフェーシングデータに対して記述する前に、テストファイルではなく、本番で n が現実的にどのくらい大きくなるのかを自問してください。n が 6 桁に達する可能性がある場合、O(n²) ソリューションはリリース前に 2 度見する必要があります。

計算量分析、ソートアルゴリズム、プロファイリングツールの詳細については、Korra Studio の Python と Computer Science セグメントを確認してください。