Computational complexity とは

コンピュータサイエンスでは、計算の複雑さ、またはアルゴリズムの複雑さは、それを実行するために必要なリソースの量です。問題の計算上の複雑さは、この問題に対するすべての可能なアルゴリズムの複雑さの最小値です(未知のアルゴリズムを含む)。
必要なリソースの量は入力に応じて変化するので、複雑さは一般に関数n→f(n)として表されます.nは入力のサイズ、f(n)は最悪の複雑度です。サイズnのすべての入力に必要なリソースの量の最大値、または平均の場合の複雑さ、つまりサイズnのすべての入力に対するリソースの量の平均です。
リソースの性質が明示的に与えられていない場合、これは通常、アルゴリズムを実行するために必要な時間であり、時間の複雑さに関するものです。しかしながら、これは使用されるコンピュータに依存し、時間は一般に所与のコンピュータ上で一定の時間を要すると考えられる基本的な動作の数として表され、コンピュータの1つが変化すると。
さもなければ、考慮されるリソースは、しばしば必要とされるメモリのサイズであり、スペースの複雑さの話があります。
明示的に与えられたアルゴリズムの複雑さの研究はアルゴリズムの分析と呼ばれ、問題の複雑さの研究は計算複雑性理論と呼ばれます。明らかに、アルゴリズムの複雑さは常にこのアルゴリズムによって解決される問題の複雑さの上限であるため、両方の領域は強く関連しています。