時間計算量【time complexity】

概要

時間計算量（time complexity）とは、コンピュータが特定の手順に従って与えられた問題を解く際に必要とする手順の回数。これが少ないほど、より短い時間で問題を解くことができる。

ある問題をコンピュータによって解くには、計算や操作、比較、分岐、繰り返しなど単純な処理を組み合わせたアルゴリズムを定義して、これをコンピュータプログラムの形で実装して実行する。その際、あるアルゴリズムが問題を解くにあたって実行しなければならない処理や操作などの回数（ステップ数）のことを時間計算量という。

具体的に必要な量は問題の要素数によって変動することが多いため、容量を要素数の式で表したときに支配的な大きさの項を用いて「O（項）」と表記することが多い（オーダー記法）。例えば、時間計算量がO（1）ならば要素数に依らず一定回数のステップが必要なアルゴリズムであり、O（n²）ならば要素数の2乗に比例してステップ数が増える。

一方、問題を解く際に占有する必要があるメモリ容量のことは空間計算量という。多くの問題は複数のアルゴリズムで解くことができ、空間計算量も時間計算量も少ないアルゴリズムが優れたアルゴリズムであると言えるが、一般的にはメモリを多く費やせば短時間で解け、長時間かければ少ないメモリ容量で済むという「時間と空間のトレードオフ」の関係が現れることが多い。

(2018.12.24更新)