最悪のケースの複雑さ

コンピュータサイエンス（特に計算複雑性理論）において、最悪ケース計算複雑性は、任意のサイズの入力（一般に漸近記法ではnと表記される）が与えられた場合にアルゴリズムに $必要$ なリソース（実行時間、メモリなど）の尺度となる。これは、アルゴリズムに必要なリソースの上限を与える。

実行時間の場合、最悪ケースの計算量とは、サイズ $nの$ 任意の入力に対してアルゴリズムが実行する最長時間を示し、指定された時間内にアルゴリズムが終了することを保証します。最悪ケースの計算量の増加順序（例えば、線形、対数）は、2つのアルゴリズムの効率を比較する際によく用いられます。

アルゴリズムの最悪ケースの複雑さは、平均ケースの複雑さ(ランダム入力に対してアルゴリズムが使用するリソース量の平均的な測定値) と対比される必要があります。

意味

計算モデルと各入力で停止するアルゴリズムが与えられた場合、すべての入力文字列に対してが正確にステップ後に停止する場合、マッピングはの時間計算量と呼ばれます。 ${\mathsf {A}}$ $s$ $t_{\mathsf {A}}\colon \{0,1\}^{\star }\to \mathbb {N}$ ${\mathsf {A}}$ $s$ ${\mathsf {A}}$ $t_{\mathsf {A}}(s)$

通常、時間計算量の異なる入力長への依存性に興味があるので、用語を乱用すると、時間計算量は、最大計算量によって定義されるマッピングと呼ばれることもあります。 $t_{\mathsf {A}}\colon \mathbb {N} \to \mathbb {N}$

t_{\mathsf {A}}(n):=\max _{s\in \{0,1\}^{n}}t_{\mathsf {A}}(s)

長さまたはサイズを持つ入力。 $s$ $\leq n$

空間複雑度、ランダム性複雑度などにも同様の定義を与えることができます。

話し方

多くの場合、アルゴリズムの複雑さは漸近的なBig-O 表記法で表されます。これは、特定の実数値の比較関数の形式で複雑さの増加率を示し、次の意味を持ちます。 $t_{\mathsf {A}}$ ${\mathsf {A}}$ $t_{\mathsf {A}}=O(g(n))$ $g(n)$

正の実数と自然数が存在し、 $M$ $n_{0}$

|t_{\mathsf {A}}(n)|\leq Mg(n)\quad {\text{すべての}}n\geq n_{0}に対して。

よくある表現は次のようになります。

「アルゴリズムは最悪のケースの複雑さを持っています。」 ${\mathsf {A}}$ $O(g(n))$

あるいは、

「アルゴリズムには複雑さがある。」 ${\mathsf {A}}$ $O(g(n))$

例

ランダムアクセスマシン上で数値の挿入ソートを実行することを考えてみましょう。このアルゴリズムの最良のケースは、数値が既にソートされている場合であり、タスクの実行にはステップが必要です。しかし、このアルゴリズムの最悪のケースでは、入力は数値が逆順にソートされている場合であり、ソートにはステップが必要です。したがって、挿入ソートの最悪のケースの時間計算量はです。 $n$ $O(n)$ $O(n^{2})$ $O(n^{2})$

参照

アルゴリズムの分析

参考文献

Thomas H. Cormen 、 Charles E. Leiserson、Ronald L. Rivest、Clifford Stein 著『アルゴリズム入門第2版』MIT Press and McGraw-Hill、2001年。ISBN 0-262-03293-7第2.2章アルゴリズムの分析、pp.25-27。
オデッド・ゴールドライヒ著『計算複雑性：概念的視点』ケンブリッジ大学出版局、2008年。ISBN 0-521-88473-X、32ページ。