コンピューティングの複雑さ-Wikipedia、無料百科事典

計算の複雑さの理論 – 計算理論部門、その主な目標は、コンピューティングの問題を解決するために必要なリソースの量を決定することです。考慮されるリソースは、時間、メモリ、またはプロセッサの数などの量です。

Juris HartmanisとRichard Stearnsは、この理論の作成者と考えられています。問題の例としてt.z.o.充足の問題、最短経路の問題、事実化の問題、および計算されることが知られている他の多くの問題を与えることができます。計算の主題は、計算理論の2番目の重要な分野である計算理論によって扱われます。

T.Z.O.によって提供される結果は、正と否定、つまり、特定の量のリソースを使用して計算することはできません。肯定的な結果は、取得が容易であり、通常、特定の問題を解決するアルゴリズムの形式と、正確性の証明と必要なリソースの説明を持っています。

アルゴリズムを作成するために必要なリソースの数は、その複雑さとして理解できます。考慮されるリソースによっては、私たちは話している 時間の複雑さ またはまた メモリの複雑さ 。もちろん、ほとんどの場合、必要なリソースの数は、特定の問題の範囲の入力データによって異なります。

たとえば、数値の素数への分布を考慮することができます。 （使用されるアルゴリズムに関係なく）数が大きいほど、それを広めるにはより多くのリソースが必要になると予測できます。この機能は、ほとんどの計算の問題で共有されています。入力データのサイズが大きいほど、計算を行うにはリソース（時間、プロセッサ、メモリ）が必要です。したがって、アルゴリズムの複雑さは、入力データサイズの関数です。

別の問題は、通常、複雑さがデータのサイズのみに依存するのではなく、同じサイズの入力データで大きく異なる場合があるという事実です。頻繁に使用される2つのアプローチ方法は次のとおりです。

一時的な計算の複雑さ [ 編集 | コードを編集します ]

採用された時間の複雑さは、入力のサイズに応じて基本操作の数です。実際のクロックタイムの測定は、アルゴリズム、使用したコンパイラ、およびアルゴリズムが作成されるマシンの実装方法に強く依存しているため、あまり役に立ちません。したがって、基本（支配的な）操作の数は通常、時間と見なされます。基本的な手術は、たとえば、置換、比較、または単純な算術手術です。

別の問題は、アルゴリズムを策定するプログラミング言語と、このアルゴリズムが実行されるマシンについて話すことにできることです。既存のコンピューターは、数学的操作によって利用可能にされるレジスタの数とサイズなどのパラメーターの重要な（アルゴリズムの構築の観点から）重要であり、絶え間ない改善の対象となります。したがって、アルゴリズムは抽象計算モデルを使用して分析されます。人気モデルには、RAMマシン、チューリングマシン、インジケーターマシンが含まれます（英語 ポインターマシン ）。

メモリコンピューティングの複雑さ [ 編集 | コードを編集します ]

時間の複雑さのように、それはアルゴリズム時間の尺度ですので、
使用されるメモリの量の測定。この量として、入力サイズ関数の抽象機械（たとえば、RAMメモリセルの数）のメモリが最も頻繁に採取されます。また、ビットまたはバイトで発現する必要な物理メモリのサイズを計算することもできます。

アルゴリズムの複雑さを比較します [ 編集 | コードを編集します ]

アルゴリズムの複雑さを比較すると、漸近成長率、つまり、小さなデータの動作を無視して、対応する大規模な境界引数（入力データサイズ）の複雑さを決定する関数を考慮します。さらに、固定されたアルゴリズムの複雑さは、アルゴリズムを実行するコンピューターの速度の影響と、あるコンピューターで迅速に実行でき、別のコンピューターで一連の指示に置き換える必要がある基本操作の選択と同じと同じと見なされます。

複雑なクラスは、同様のコンピューティングの複雑さを伴う計算問題のクラスです。つまり、同様の量のリソースを解決する必要がある問題は、クラスで結合します。たとえば、必要なメモリの量がデータのサイズに対して直線的に増加する場合、線形メモリの複雑さに関する問題について話しています。または、基本操作の数がデータサイズの平方に増加する場合、平方時間の複雑さの問題について。また、アルゴリズムに同様の用語を使用します。

また、クラスPなどの幅広い概念を使用します。たとえば、それぞれ、回答が肯定的である場合、多項式検証の対象となる多項式および意思決定の問題を決定する問題を決定します。

問題は、Pクラスが、たとえばミレニアム問題の1つであり、100万ドルの賞金が提供されているのかと同じかどうかです。各Pの問題もクラスにあります。

3つの可能な解決策があります。

• クリストスH.パパディミトリウ： 計算の複雑さ 、Wnt 2002。
• クリストスH.パパディミトリウ： 計算の複雑さ 、新しい翻訳（ZdzisławPłoskiによる翻訳）。 Helion 2012。
• T. H. Cormen、C。E。Leiserson、C。SteinI R. L. Rivest、 アルゴリズムの概要 、The Mit Press/McGraw-Hill Company 1990（ポーランド版： アルゴリズムの概要 、Wnt 2004）。
• マレク・クバレ： アルゴリズムの分析の穏やかな紹介 、Gdañsk2004。