計算の複雑さの理論 – 計算理論部門、その主な目標は、コンピューティングの問題を解決するために必要なリソースの量を決定することです。考慮されるリソースは、時間、メモリ、またはプロセッサの数などの量です。 Juris HartmanisとRichard Stearnsは、この理論の作成者と考えられています。問題の例としてt.z.o.充足の問題、最短経路の問題、事実化の問題、および計算されることが知られている他の多くの問題を与えることができます。計算の主題は、計算理論の2番目の重要な分野である計算理論によって扱われます。 T.Z.O.によって提供される結果は、正と否定、つまり、特定の量のリソースを使用して計算することはできません。肯定的な結果は、取得が容易であり、通常、特定の問題を解決するアルゴリズムの形式と、正確性の証明と必要なリソースの説明を持っています。 アルゴリズムを作成するために必要なリソースの数は、その複雑さとして理解できます。考慮されるリソースによっては、私たちは話している 時間の複雑さ またはまた メモリの複雑さ 。もちろん、ほとんどの場合、必要なリソースの数は、特定の問題の範囲の入力データによって異なります。 たとえば、数値の素数への分布を考慮することができます。 (使用されるアルゴリズムに関係なく)数が大きいほど、それを広めるにはより多くのリソースが必要になると予測できます。この機能は、ほとんどの計算の問題で共有されています。入力データのサイズが大きいほど、計算を行うにはリソース(時間、プロセッサ、メモリ)が必要です。したがって、アルゴリズムの複雑さは、入力データサイズの関数です。 別の問題は、通常、複雑さがデータのサイズのみに依存するのではなく、同じサイズの入力データで大きく異なる場合があるという事実です。頻繁に使用される2つのアプローチ方法は次のとおりです。 一時的な計算の複雑さ [ 編集 | コードを編集します
Continue reading
Recent Comments