Time complexity とは

コンピュータサイエンスでは、時間の複雑さは、アルゴリズムを実行するのに要する時間を表す計算上の複雑さです。時間の複雑さは、一般に、各基本操作が実行するのに一定の時間がかかると仮定して、アルゴリズムによって実行される基本操作の数を数えることによって推定される。したがって、取られた時間の長さおよびアルゴリズムによって実行される基本的な操作の数は、せいぜい一定の係数だけ異なるように取られる。
アルゴリズムの実行時間は同じサイズの異なる入力間で異なることがあるので、所与のサイズの入力に必要とされる最大時間である最悪の時間複雑度を考慮する。あまり一般的ではなく、通常は明示的に指定されているのは、平均的な場合の複雑さです。これは、指定されたサイズの入力にかかる時間の平均です(これは、指定されたサイズの可能な入力が限られているためです)。どちらの場合でも、時間の複雑さは一般に入力のサイズの関数として表されます。この関数は一般的に正確に計算するのが難しく、小さな入力の実行時間は通常重要ではないため、入力サイズが大きくなるときの複雑さ、つまり複雑さの漸近的な振る舞いによく焦点を合わせます。したがって、時間の複雑さは一般にbig O表記法、一般的に O ( n ) , {\displaystyle O(n),} O ( n log n ) , {\displaystyle O(n\log n),} O ( n α ) , {\displaystyle O(n^{\alpha }),} O ( 2 n ) , {\displaystyle O(2^{n}),} などで表されます。ここで、nは入力を表すのに必要なビット単位の入力サイズです。
アルゴリズムの複雑さは、ビッグO表記に現れる関数のタイプによって分類されます。例えば、時間複雑度 O ( n ) {\displaystyle O(n)} のアルゴリズムは線形時間アルゴリズムであり、ある一定の α > 1 {\displaystyle \alpha >1} の時間複雑度 O ( n α ) {\displaystyle O(n^{\alpha })} を持つアルゴリズムは多項式時間アルゴリズムである。