ベスト、ワースト、& 平均ケース
アルゴリズムの三つの測定方法
すべてのアルゴリズムのコストは、その入力によって決まります。同じサイズの二つの入力は、異なる実行時間を生み出すことがあります。複雑性分析は、その変動に対する三つの視点を形式化します。
最良の場合 — Ω (オメガ): アルゴリズムが最短で終了する入力。線形検索がN個の要素のリスト上で: Ω(1) — ターゲットはリストの最初の位置にある。1つの比較、終了。
最悪の場合 — O (ビッグオー): アルゴリズムが最も遅く終了する入力。線形検索: O(N) — ターゲットはリストの最後に位置しているか、リストに登場しない。すべての要素が検査される必要があります。
平均的な場合 — Θ (シータ): すべての可能な入力に対する予想されるコスト、均等な分布を仮定する場合。ターゲットがNの位置のいずれにも等確率で登場する線形検索: Θ(N/2) = Θ(N)。定数1/2は、シータはあсимプトット的成長のtightな境界を表し、正確な係数ではなく、dropされます。
最悪の場合が支配する理由
システムは、最悪の場合を処理する必要があります。データベースクエリが平均して10msで、まれに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(N)の追加メモリを使用してO(1)の検索を達成します。ハッシュテーブルがない場合、リストをスキャンしてO(N)の検索を達成し、O(1)の追加メモリが必要です。ハッシュテーブルはメモリを支払い、スピードを買います。
メモ化は、以前計算した結果（O(N)またはそれ以上のスペース）を再計算を避けるために保存します。再帰的Fibonacciの場合、メモ化なしではO(2^N)の時間で、メモ化ありではO(N)の時間とO(N)のスペースです。スペースの投資は時間を指数関数的に減らします。
ハッシュ辞書とソート済みリスト
2つの単語出現カウント戦略を比較してください：N単語の文書中でどうやって行いますか？
戦略A: 辞書（ハッシュマップ）。各単語を挿入し、カウントをインクリメントします。
戦略B: 見たことのある単語の並べられたリストを維持します。バイナリ検索を使用して、メンバーの存在を確認する前に挿入します。
アモルタ化分析：コストを均等に分散
まれな費用が平均的なパフォーマンスを台無しにすることはない時
ある操作がまれに高額である場合、そのシーケンス全体の平均的なコストで安価である場合があります。アモルタ化分析は、シーケンス全体の平均的なコスト（1操作あたり）を計算しますが、単一の操作の最悪の場合のコストではありません。
ダイナミック配列（Pythonリスト、Java ArrayList）： 1のキャパシティで開始します。満タンになると、キャパシティを2倍にします。倍増は既存のすべての要素をコピーするため、1つのappendでO(N)の作業が行われます。しかし、倍増はまれです。N個の総appendの後に、総コピー操作がどれだけ発生したかを計算してください？
倍増はサイズ1、2、4、8、...、N/2で発生します。コピーのカウントは、1 + 2 + 4 + ... + N/2です。これは、N − 1の総コピーをすべてのNのインサートで持つ傾向があります。平均的なコピーあたり：(N − 1) / N < 1なので、O(1)アモルタ化でそれぞれのappendに、それぞれの倍増のO(N)最悪の場合のコストよりも少なくなる。
なぜアモルタ化分析が重要か
システムがまれにリサイズ、再バランス、またはコンパクト構造を停止する場合、個々の操作の最悪の場合のO(N)コストが見えてしまうかもしれません。アモルタ化分析では、警告は誤りであることがわかります。多くの安価なイベントがまれに高額なイベントを支払うことで、誤った警告は解消されます。アモルタ化コストを理解することで、オーバーエンジニアリングを防ぎます：まれなO(N)操作を避けるために、オニオンコストがアモルタ化するだけの複雑さを追加するのは無駄です。
深掘り: ハミングなしコースでは、実世界のデフォルトで生産ソフトウェアに複雑性分析を適用します。[アルゴリズム複雑性の見えない章](/en/un/unhamming_algorithmic_complexity)および[MOAD-0001:堆積物欠陥](/en/un/unhamming_moad_sedimentary)を参照してください。
ハッシュテーブルのアモルタ化挿入
ハッシュテーブルは空で開始し、負荷係数が0.75を超える場合にキャパシティを倍にします。1,000の要素を挿入することで、正確に10回のダブリングがトリガーされ、キャパシティは1、2、4、8、16、32、64、128、256、512になります。