計算複雑性

コンピュータサイエンスにおいて、アルゴリズムの計算複雑度、あるいは単に複雑度とは、そのアルゴリズムを実行するために必要なリソースの量を指します。^{[ 1 ]}特に、計算時間（一般的には必要な基本演算の数で測定される）とメモリの記憶容量要件に重点が置かれます。問題の複雑度とは、その問題を解決できる最良のアルゴリズムの複雑度を指します。

明示的に与えられたアルゴリズムの複雑さを研究することをアルゴリズム解析と呼び、問題の複雑さを研究することを計算複雑性理論と呼びます。アルゴリズムの複雑さは常にそのアルゴリズムによって解決される問題の複雑さの上限となるため、両分野は密接に関連しています。さらに、効率的なアルゴリズムを設計するには、特定のアルゴリズムの複雑さを解決すべき問題の複雑さと比較することがしばしば不可欠です。また、ほとんどの場合、問題の複雑さについて分かっているのは、それが最も効率的な既知のアルゴリズムの複雑さを超えないということだけです。したがって、アルゴリズム解析と計算複雑性理論の間には大きな重複があります。

アルゴリズムを実行するために必要なリソースの量は一般的に入力のサイズによって変化するため、複雑さは通常、関数n ↦ f ( n )として表されます。ここで、nは入力のサイズであり、f ( n )は最悪の場合の複雑さ(サイズnのすべての入力で必要とされるリソース量の最大値) または平均の場合の複雑さ(サイズnのすべての入力で必要とされるリソース量の平均) のいずれかです。時間計算量は一般的に、サイズnの入力に必要な基本操作の数として表されます。ここで、基本操作は、特定のコンピュータで一定の時間を要し、別のコンピュータで実行された場合でも一定の係数だけ変化すると想定されます。空間計算量は一般的に、サイズnの入力に対してアルゴリズムが必要とするメモリ量として表されます。

アルゴリズムのステップ数を、考えられるすべての入力に対して数えることは不可能です。一般的に、入力のサイズが大きくなるにつれて複雑さも増すため、複雑さは通常、入力のサイズn (ビット単位) の関数として表され、したがって、複雑さはnの関数となります。しかし、同じサイズの入力であっても、アルゴリズムの複雑さは大きく異なる場合があります。そのため、複数の複雑さ関数が一般的に使用されます。

最悪ケースの複雑度は、サイズnのすべての入力に対する複雑度の最大値であり、平均ケースの複雑度は、サイズnのすべての入力に対する複雑度の平均値です（これは、特定のサイズの入力の数が有限であるため、理にかなっています）。一般に、「複雑度」という言葉が特に指定されずに使用される場合、それは最悪ケースの時間計算量を指します。

最悪の場合と平均的な場合の計算量を正確に算出することは一般的に困難です。さらに、これらの正確な値は、コンピュータや計算モデルの変更によって計算量が多少変化するため、実用的な用途はほとんどありません。また、nの値が小さい場合、リソースの使用量はそれほど重要ではないため、 nが小さい場合は、一般的に低い計算量よりも実装の容易さの方が重要になります。

こうした理由から、一般的にはnが大きい場合の計算量の挙動、すなわちnが無限大に近づくときの漸近的な挙動に注目する。そのため、計算量は一般的にビッグオー記法を用いて表現される。

例えば、整数乗算の通常のアルゴリズムの計算量は${\displaystyle O(n^{2});}$これは定数が存在することを意味します${\displaystyle c_{u}}$最大n桁の 2 つの整数の乗算を以下の時間未満で実行できる${\displaystyle c_{u}n^{2}.}$この境界は、最悪の場合の複雑さと平均的な場合の複雑さが次のようになるという意味で厳密である。${\displaystyle \Omega (n^{2}),}$つまり、定数も存在するということだ${\displaystyle c_{l}}$これらの複雑さは、${\displaystyle c_{l}n^{2}.}$基数はこれらの複雑な式には現れません。基数を変更しても定数のみが変わるからです。${\displaystyle c_{u}}$そして${\displaystyle c_{l}.}$

計算の複雑さの評価は、単位時間内に実行される基本演算を定義する計算モデルの選択に依存します。計算モデルが明示的に指定されていない場合、一般的にはマルチテープチューリングマシンであると暗黙のうちに想定されます。これは、ランダムアクセスマシンなど、より現実的な計算モデルの多くが、ほとんどの問題で漸近的に等価であるためです。これは、整数乗算のような非常に特殊で困難な問題にのみ適用されます。${\displaystyle O(n\log n),}$証明には計算モデルの明示的な定義が必要である。

非公式には、問題の複雑さとは、未知のアルゴリズムも含め、その問題を解決するすべてのアルゴリズムの中で最小の複雑さを指しますが、そのような最小の複雑さは存在しない場合もあります。したがって、問題の複雑さは、その問題を解決するどのアルゴリズムの複雑さよりも大きくなることはありません。

したがって、ビッグオー記法で表現されるアルゴリズムの複雑さはすべて、対応する問題の複雑さの上限でもある。

一方で、問題の複雑さに対する非自明な下限値を得ることは一般的に難しく、そのような下限値を得るための方法はほとんどない。

ほとんどの問題を解決するには、すべての入力データを読み込む必要があり、通常、データのサイズに比例した時間が必要です。したがって、このような問題の複雑さは少なくとも線形であり、つまり、ビッグオメガ表記法を使用すると、複雑さは${\displaystyle \Omega (n).}$

コンピュータ代数や計算代数幾何学など、一部の問題の解は非常に大きくなる場合があります。このような場合、出力を書き出す必要があるため、複雑さは出力の最大サイズによって下限が定められます。たとえば、n個の不定元に関する次数dのn個の多項式方程式のシステムは、最大で次のようになります。$d^n$解の数が有限であれば、解は複雑になります（これはベズーの定理です）。これらの解を書き出す必要があるため、この問題の複雑さは${\displaystyle \Omega (d^{n}).}$この問題に対して、複雑度のアルゴリズム$d^{O(n)}}$は既知であり、したがって漸近的に最適であると考えられる。

非線形下限${\displaystyle \Omega (n\log n)}$は、ソートアルゴリズムに必要な比較回数を表します。したがって、最適なソートアルゴリズムは、その複雑さが であるため、漸近的に最適です。${\displaystyle O(n\log n).}$この下限は、n 個のオブジェクトを順序付ける方法がn !通りあるという事実から生じます。各比較によってこのn !通りの順序の集合が 2 つの部分に分割されるため、すべての順序を区別するために必要な比較の数Nは、${\displaystyle 2^{N}>n!,}$これはつまり${\displaystyle N=\オメガ (n\log n),}$スターリングの公式による。

問題の複雑性の下限を示す標準的な方法は、問題を別の問題に還元することです。より正確には、サイズnの問題Aを問題Bのサイズf ( n )の部分問題にエンコードできると仮定し、 Aの複雑性は${\displaystyle \Omega (g(n)).}$一般性を失うことなく、関数fはnとともに増加し、逆関数hを持つと仮定できる。すると、問題Bの複雑さは次のようになる。${\displaystyle \Omega (g(h(n))).}$これは、 P ≠ NP (未解決の予想) の場合、すべてのNP 完全問題の複雑さが次のようになることを証明するために使用される方法です。${\displaystyle \Omega (n^{k}),}$すべての正の整数kに対して。

アルゴリズムの複雑さを評価することは、アルゴリズム設計において重要な部分であり、期待されるパフォーマンスに関する有用な情報を提供する。

ムーアの法則（現代のコンピュータの処理能力が指数関数的に増加するという法則）によって、アルゴリズムの複雑さの評価の重要性が低下するという誤解がよく見られます。しかし、これは間違いです。なぜなら、この処理能力の向上によって、大量の入力データ（ビッグデータ）を扱うことが可能になるからです。例えば、数百件のエントリからなるリスト（書籍の参考文献など）をアルファベット順に並べ替える場合、どのようなアルゴリズムでも1秒以内に処理を完了できます。一方、100万件のエントリからなるリスト（例えば、大都市の電話番号など）の場合、基本的なアルゴリズムでは処理に膨大な時間がかかります。${\displaystyle O(n^{2})}$比較を行うには 1 兆回の比較が必要となり、1 秒あたり 1000 万回の比較の速度で約 3 時間かかる。一方、クイックソートとマージソートではわずか 1 秒で済む。${\displaystyle n\log _{2}n}$比較回数（前者の場合は平均ケースの複雑さ、後者の場合は最悪のケースの複雑さ）。n = 1,000,000 の場合、約30,000,000 回の比較が行われ、1 秒あたり 1000 万回の比較であればわずか 3 秒で済みます。

このように、複雑性の評価によって、実装前に多くの非効率なアルゴリズムを排除することが可能になります。また、すべてのバリエーションをテストすることなく、複雑なアルゴリズムを調整するためにも利用できます。複雑性の研究は、複雑なアルゴリズムの中で最もコストのかかるステップを特定することで、実装の効率改善のための取り組みをこれらのステップに集中させることを可能にします。

• 数学演算の計算複雑性
• 中国の郵便配達員問題の複雑性リスト
• マスター定理（アルゴリズムの解析）

• Arora, Sanjeev ; Barak, Boaz (2009), Computational Complexity: A Modern Approach , Cambridge , ISBN 978-0-521-42426-4、Zbl 1193.68112 
• Calude, Cristian (1988), Theories of Computational Complexity , Elsevier , p.  487, ISBN 9780444703569
• 杜、丁珠。 Ko、Ker-I (2000)、計算複雑性の理論、John Wiley & Sons、ISBN 978-0-471-34506-0ISSN 0167-5060​ 
• Garey, Michael R. ; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , Series of Books in the Mathematical Sciences (1st  ed.), New York: WH Freeman and Company , ISBN 9780716710455MR 0519066、OCLC 247570676​  
• ゴールドライヒ、オデッド（2008）、『計算複雑性：概念的視点』、ケンブリッジ大学出版局
• van Leeuwen, Jan編 (1990)、『理論計算機科学ハンドブック（A巻）：アルゴリズムと複雑性』、MIT Press、ISBN 978-0-444-88071-0
• パパディミトリウ、クリストス（1994）、『計算複雑性』（第1 版）、アディソン・ウェスリー、ISBN 0-201-53082-1
• Sipser, Michael (2006), 『計算理論入門』（第2 版）、米国：Thomson Course Technology、ISBN 0-534-95097-3