漸近的計算複雑性

計算複雑性理論において、漸近的計算複雑性とは、漸近解析を使用してアルゴリズムや計算問題の計算複雑性を推定することであり、通常はビッグ O 表記法の使用に関連付けられます。

計算リソースに関しては、漸近的な時間計算量と漸近的な空間計算量が一般的に推定されます。その他の漸近的に推定される動作には、回路の複雑さや、 （並列）プロセッサの数などの 並列計算のさまざまな尺度が含まれます。

1965年にJuris HartmanisとRichard E. Stearnsが発表した画期的な論文^{[1]と、1979年に}Michael GareyとDavid S. Johnsonが発表したNP完全性に関する書籍^[2]以来、 「計算複雑性」（アルゴリズムの）という用語は、漸近的計算複雑性と呼ばれるようになりました。

さらに、特に指定がない限り、「計算の複雑さ」という用語は通常、アルゴリズムまたは問題の漸近的な計算の複雑さの上限を指し、通常はビッグ O 表記法で表されます (例)。その他の種類の (漸近的な) 計算の複雑さの推定には、下限(「ビッグ オメガ」表記法、例: Ω( n )) と、漸近的な上限と下限が一致する漸近的に厳密な推定値 (「ビッグ シータ」を使用して表されます (例: Θ( n log n ))) があります。 ${\displaystyle O(n^{3}).}$

さらに暗黙の前提として、特に明記しない限り、計算の複雑さの最悪ケースの分析が問題となる。別のアプローチとしては、アルゴリズムの確率的分析がある。

理論計算機科学では非決定論的アルゴリズムやその他の高度な計算モデルも考慮されますが、実際のケースではほとんどの場合、決定論的アルゴリズムまたはランダム化アルゴリズムが議論されます。

• 漸近最適アルゴリズム