計算の複雑さ

コンピュータサイエンスでは、計算の複雑さ、または単にアルゴリズムの複雑さは、それを実行するのに必要なリソースの量です。^[1]特に、計算時間（通常は必要な基本操作の数で測定されます）とメモリストレージ要件に重点が置かれています。問題の複雑さは、問題を解決できる最良のアルゴリズムの複雑さです。

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

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

最も一般的に考慮されるリソースは時間です。「複雑さ」が限定なしで使用されている場合、これは通常、時間の複雑さを意味します。

通常の時間単位 (秒、分など) は、特定のコンピュータの選択と技術の進化に大きく依存するため、複雑性理論では使用されません。たとえば、今日のコンピュータは 1960 年代のコンピュータよりも大幅に高速にアルゴリズムを実行できますが、これはアルゴリズムの本質的な特徴ではなく、コンピュータ ハードウェアの技術的進歩の結果です。複雑性理論は、アルゴリズムの本質的な時間要件、つまりアルゴリズムがコンピュータに課す基本的な時間制約を定量化しようとします。これは、計算中に実行される基本操作の数を数えることによって実現されます。これらの操作は、特定のマシン上で一定時間 (つまり、入力のサイズによって影響されない) かかると想定されており、ステップと呼ばれることがよくあります。

正式には、ビット複雑度は、アルゴリズムを実行するために必要なビットの操作の数を指します。ほとんどの計算モデルでは、ビット複雑度は定数倍までの時間複雑度に等しくなります。コンピューターでは、必要なマシンワードの操作数もビット複雑度に比例します。したがって、現実的な計算モデルでは、 時間複雑度とビット複雑度は等しくなります。

もう 1 つの重要なリソースは、アルゴリズムの実行に必要な コンピュータ メモリのサイズです。

複数の相互作用する当事者によって一般的に実行される分散アルゴリズムのクラスの場合、最も重要なリソースは通信の複雑さです。これは、実行当事者間の必要な通信量です。

算術演算の回数は、よく使用される別のリソースです。この場合、算術計算の複雑さについて言及します。計算中に発生する数値のバイナリ表現のサイズの上限がわかっている場合、時間の複雑さは一般に、算術計算の複雑さと定数係数の積になります。

多くのアルゴリズムでは、計算中に使用される整数のサイズは制限されておらず、算術演算に一定の時間がかかると考えるのは現実的ではありません。したがって、この文脈では一般にビット複雑度と呼ばれる時間の計算量は、算術複雑度よりもはるかに大きくなる可能性があります。たとえば、n × n整数行列の行列式の計算の算術複雑度は、通常のアルゴリズム (ガウス消去法) の場合です。同じアルゴリズムのビット複雑度はnに対して指数関数的です。これは、計算中に係数のサイズが指数的に増加する可能性があるためです。一方、これらのアルゴリズムをマルチモジュラ算術と組み合わせると、ビット複雑度はO ^~ ( n ⁴ )に削減される可能性があります。 ${\displaystyle O(n^{3})}$

ソートと検索では、一般的に考慮されるリソースはエントリ比較の数です。データが適切に整理されている場合、これは通常、時間の複雑さを測るのに適した指標です。

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

最悪ケースの複雑さは、サイズnのすべての入力の複雑さの最大値であり、平均ケースの複雑さは、サイズnのすべての入力の複雑さの平均です(特定のサイズの可能な入力の数は有限であるため、これは理にかなっています)。一般に、「複雑さ」がさらに指定されずに使用される場合、これは考慮される最悪のケースの時間複雑さです。

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

これらの理由から、一般的にはn が大きい場合の計算量の挙動、つまりn が無限大に近づくときの漸近的な挙動に焦点が当てられます。したがって、計算量は一般にビッグオー記法を使用して表現されます。

例えば、整数乗算の通常のアルゴリズムの複雑度は であり、これは、最大でn桁の 2 つの整数の乗算が より短い時間で実行できる定数が存在することを意味します。この境界は、最悪の場合の複雑度と平均的な場合の複雑度が であるという意味において明確であり、これは、これらの複雑度が より大きい定数が存在することを意味します。基数はこれらの複雑度には現れません。基数を変更しても定数のみが変化するためです。${\displaystyle O(n^{2}),}$${\displaystyle c_{u}}$${\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),}$

決定論的計算モデルとは、マシンの連続状態と実行される操作が、前の状態によって完全に決定される計算モデルです。歴史的に、最初の決定論的モデルは、再帰関数、ラムダ計算、チューリングマシンでした。ランダムアクセスマシン（RAMマシンとも呼ばれる）のモデルも、実際のコンピュータに近いものとして広く使用されています。

計算モデルが指定されていない場合は、通常、マルチテープ チューリング マシンであると想定されます。ほとんどのアルゴリズムでは、マルチテープ チューリング マシンと RAM マシンの時間計算量は同じですが、この同等性を実現するには、データをメモリに格納する方法に多少の注意が必要になる場合があります。

非決定性チューリングマシンなどの非決定性計算モデルでは、計算のいくつかのステップでいくつかの選択が行われることがあります。計算量理論では、すべての可能な選択を同時に検討し、非決定性時間計算量とは、常に最良の選択が行われる場合に必要な時間です。言い換えると、計算は必要な数の（同一の）プロセッサで同時に行われると考え、非決定性計算時間とは、計算を終えた最初のプロセッサが費やす時間です。この並列処理は、特定の量子アルゴリズムを実行する際の重ね合わせたエンタングルメント状態を介して、部分的に量子コンピューティングに適しています。たとえば、ショアの因数分解（2018年3月現在：21 = 3 × 7）などです。 ^{[アップデート]}

このような計算モデルはまだ現実的ではないが、理論的には重要であり、主にP = NP問題に関連している。この問題は、「多項式時間」と「非決定性多項式時間」を最小上限として形成される複雑性クラスの同一性を問うものである。NP アルゴリズムを決定性コンピュータでシミュレートするには、通常「指数時間」がかかる。問題が非決定性マシンで多項式時間で解決できる場合、その問題は複雑性クラスNPに属する。問題がNP 完全であるとは、大まかに言えば、NP に属し、他のどの NP 問題よりも簡単でない場合である。ナップザック問題、巡回セールスマン問題、ブール充足問題など、多くの組み合わせ問題はNP 完全である。これらすべての問題において、最もよく知られているアルゴリズムは指数複雑性を持つ。これらの問題のいずれかが決定論的マシン上で多項式時間で解決できる場合、すべての NP 問題も多項式時間で解決でき、P = NP になります。2017 年現在、P ≠ NPであると一般に推測されており、 NP 問題の最悪のケースは本質的に解決が困難である、つまり、興味深い長さの入力に対して合理的な時間範囲 (数十年!) よりも長い時間がかかるという実際的な意味合いがあります。 ^{[アップデート]}

並列コンピューティングと分散コンピューティングは、同時に動作する複数のプロセッサに計算を分割することで構成されます。異なるモデル間の違いは、主にプロセッサ間で情報を転送する方法にあります。通常、並列コンピューティングではプロセッサ間のデータ転送は非常に高速ですが、分散コンピューティングではデータ転送はネットワーク経由で行われるため、はるかに低速になります。

N 個のプロセッサで計算を行うのに必要な時間は、少なくとも 1 個のプロセッサで必要な時間のN倍になります。実際には、一部のサブタスクは並列化できず、一部のプロセッサは別のプロセッサからの結果を待たなければならないため、この理論的に最適な境界に達することは決してありません。

したがって、主な複雑さの問題は、計算時間とプロセッサ数の積が、単一のプロセッサ上で同じ計算を実行するために必要な時間に可能な限り近くなるようにアルゴリズムを設計することです。

量子コンピュータは、計算モデルが量子力学に基づいたコンピュータです。量子コンピュータにはチャーチ＝チューリングのテーゼが適用されます。つまり、量子コンピュータで解決できるすべての問題は、チューリングマシンでも解決できます。ただし、理論的には、一部の問題は、古典コンピュータではなく量子コンピュータを使用すると、はるかに低い時間計算量で解決できる可能性があります。現時点では、効率的な量子コンピュータの構築方法を誰も知らないため、これは純粋に理論的なものです。

量子複雑性理論は、量子コンピュータを使用して解決される問題の複雑性クラスを研究するために開発されました。これは、量子コンピュータによる攻撃に耐性のある暗号化プロトコルの設計からなるポスト量子暗号で使用されます。

問題の複雑さは、その問題を解決できる可能性のあるアルゴリズムの複雑さの下限値です^[要出典]。これには未知のアルゴリズムも含まれます。したがって、問題の複雑さは、その問題を解決するアルゴリズムの複雑さよりも大きくなることはありません。

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

一方、問題の複雑さに対して重要な下限値を得ることは一般に困難であり、そのような下限値を得る方法もほとんどありません。

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

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

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

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

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

ムーアの法則は、現代のコンピュータの性能が指数関数的に増大することを前提としており、その結果、アルゴリズムの複雑さの評価はそれほど重要ではなくなるという誤解がよくあります。しかし、この性能増大により、大量の入力データ (ビッグデータ) を扱えるようになるため、これは誤りです。たとえば、本の参考文献など、数百のエントリのリストをアルファベット順にソートする場合、どのアルゴリズムでも 1 秒未満で処理できるはずです。一方、100 万のエントリ (たとえば、大都市の電話番号) のリストの場合、比較を必要とする基本的なアルゴリズムでは 1 兆回の比較を行う必要があり、1 秒あたり 1,000 万回の比較の速度で約 3 時間かかります。一方、クイックソートとマージソートでは、比較のみが必要です(前者の場合は平均的な複雑さ、後者の場合は最悪の複雑さ)。n = 1,000,000の場合、約 30,000,000 回の比較が行われ、1 秒あたり 1000 万回の比較では 3 秒しかかかりません。 ${\displaystyle O(n^{2})}$${\displaystyle n\log_{2}n}$

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

• 数学演算の計算複雑性
• 中国郵便配達問題の複雑さリスト

• アローラ、サンジーヴ、バラク、ボアズ（2009）、計算複雑性：現代的アプローチ、ケンブリッジ、ISBN 978-0-521-42426-4、Zbl  1193.68112
• カルード、クリスティアン（1988）、計算複雑性の理論、エルゼビア、p. 487、ISBN 9780444703569
• 杜、丁珠。 Ko、Ker-I (2000)、計算複雑性の理論、John Wiley & Sons、ISBN 978-0-471-34506-0、ISSN  0167-5060
• ゲーリー、マイケル R. ;ジョンソン、デビッド S. (1979)。コンピュータと扱いにくさ: NP 完全性理論ガイド。数学科学シリーズ (第 1 版)。ニューヨーク: WH フリーマン アンド カンパニー。ISBN 9780716710455. MR  0519066. OCLC  247570676.
• ゴールドライヒ、オデッド（2008）、計算複雑性：概念的視点、ケンブリッジ大学出版局
• van Leeuwen, Jan編 (1990)、理論計算機科学ハンドブック (第 A 巻): アルゴリズムと複雑性、MIT Press、ISBN 978-0-444-88071-0
• パパディミトリウ、クリストス（1994）、計算複雑性（第1版）、アディソン・ウェスリー、ISBN 0-201-53082-1
• シプサー、マイケル（2006）、計算理論入門（第2版）、米国：トムソンコーステクノロジー、ISBN 0-534-95097-3