ベストケース、ワーストケース、平均ケース
アルゴリズムを測定する3つの方法
すべてのアルゴリズムのコストはその入力に依存します。同じサイズの2つの入力は、大きく異なる実行時間を生成できます。計算量解析は、その変動に関する3つの視点を形式化します。
最良ケース — Ω（オメガ）： アルゴリズムを最も速く完了させる入力です。N個のアイテムのリストに対する線形探索の場合：Ω(1)—ターゲットは最初の位置にあります。1回の比較で完了します。
最悪ケース — O（ビッグオー）： アルゴリズムを最も遅く完了させる入力です。線形探索の場合：O(N)—ターゲットはリストの最後にあるか、まったく表示されません。すべての要素を検査する必要があります。
平均ケース — Θ（シータ）： 均等分布を仮定して、可能なすべての入力にわたる予想コストです。ターゲットがN個の位置のいずれにでも等しく置かれる可能性がある線形探索の場合：Θ(N/2) = Θ(N)。定数1/2は省略されます。シータは厳密な漸近成長を表現し、正確な係数ではないためです。
なぜ最悪ケースが支配するのか
システムは最悪ケースを処理する必要があります。平均10ミリ秒だが時々60秒かかるデータベースクエリは、ユーザーに見える失敗を引き起こします。エンジニアは入力に関係なくパフォーマンスが予測可能なままになるように、最悪ケースの境界に合わせて設計します。平均ケース分析は確率的設定で価値がありますが、最悪ケース分析は保証を与えます。
二分探索のケース分析
二分探索はソートされた配列でのみ機能します。各ステップで：ターゲットを中点の要素と比較します。ターゲットが中点と等しい場合は、それを返します。ターゲットがより小さい場合は、左半分で再帰します。より大きい場合は、右半分で再帰します。
各比較は残りの候補の半分を削除します。
メモリ成長と時間空間トレードオフ
操作ではなくメモリをカウント
時間計算量はアルゴリズムが実行する操作の数を測定します。空間計算量は入力を超えて割り当てる余分なメモリを測定します。どちらも本番システムで重要です：O(N²)メモリを割り当てる高速アルゴリズムはサーバーを枯渇させます。
O(1)空間： Nに関係なく定数の余分なメモリ。インプレースソート（例：挿入ソート）は元の配列内の要素をスワップします。いくつかの一時変数を使用します—配列がどれだけ大きくてもO(1)です。
O(N)空間： メモリは入力サイズに比例します。N要素の配列のコピーを作成するにはNスロットが必要です。N個の文字列のリストからハッシュセットを構築すると、最大N個のエントリが格納されます。
O(N²)空間： メモリはN²に比例します。N個の頂点を持つグラフのN×N隣接行列を構築するにはN²セルが必要です。N = 10,000頂点の場合、それは10^8エントリです—単純なブール値グリッドで数百メガバイト。
時間空間トレードオフ
アルゴリズム設計の基本的な動きの1つ：空間を時間と交換するか、時間を空間と交換します。
ハッシュテーブルはO(1)ルックアップを達成するためにO(N)の余分な空間を使用します。ハッシュテーブルなしで、リストの走査はO(1)の余分な空間でO(N)ルックアップを達成します。ハッシュテーブルはメモリを支払ってスピードを買います。
メモ化は以前に計算された結果（O(N)以上の空間）を格納して、それらを再計算することを避けます。メモ化なしの再帰フィボナッチはO(2^N)時間で実行されます。メモ化付き：O(N)時間およびO(N)空間。空間投資は時間を指数関数的に縮小します。
ハッシュ辞書とソート済みリスト
N個の単語のドキュメント内の単語の出現をカウントするための2つの戦略を比較してください：
戦略A： 辞書（ハッシュマップ）。各単語を挿入します。カウントを増やします。
戦略B： 見た単語のソート済みリストを維持します。挿入する前にバイナリ検索を使用してメンバーシップをチェックします。
償却分析：コストの分散
時々の費用が平均的なパフォーマンスを台無しにしない場合
一部の操作は時々高価ですが、シーケンス全体では平均的には安いです。償却分析はシーケンス全体にわたる操作あたりの平均コストを計算します—単一の操作の最悪ケースコストではなく。
動的配列（Pythonリスト、JavaArrayList）： 容量1で開始します。満杯の場合、容量を倍にします。ダブリングはすべての既存要素をコピーします：1つの追加でO(N)の作業。しかし、ダブリングはまれです。合計N個の追加の後、合計いくつのコピー操作が発生しましたか？
ダブリングはサイズ1、2、4、8、...、N/2で発生します。コピー数：1 + 2 + 4 + ... + N/2。これはすべてのN個の追加にわたってN−1個の合計コピーに合計する幾何級数です。追加あたりの平均コピー：(N − 1) / N < 1、したがって追加あたり償却O(1)（ダブリングあたりの最悪ケースコストO(N)にもかかわらず）。
なぜ償却分析が重要なのか
時々サイズ変更、リバランス、または構造の圧縮を一時停止するシステムは、警告的な最悪ケースの個別の操作を持つように見える場合があります。償却分析はアラームが偽であることを明かします：まれな高価なイベントは多くの安いものによって支払われます。償却コストを理解することは過度なエンジニアリングを防ぎます：償却O(1)のみに貢献するまれなO(N)操作を避けるために複雑さを追加することは無駄な仕事です。
より深く： unhamming コースは本番ソフトウェアの現実世界の欠陥に計算量解析を適用します。不足している章：アルゴリズム複雑性 & MOAD-0001：堆積的欠陥を参照してください。
ハッシュテーブル償却挿入
ハッシュテーブルは空で始まり、負荷係数が0.75を超えるたびに容量を倍にします。1,000個の要素を挿入すると、容量1、2、4、8、16、32、64、128、256、512で正確に10回のダブリングがトリガーされます。