時間計算量

理論計算機科学において、時間計算量とは、アルゴリズムを実行するのにかかる計算機時間を表す計算量です。時間計算量は通常、各基本操作の実行に一定の時間がかかるものと仮定して、アルゴリズムによって実行される基本操作の数を数えることによって推定されます。したがって、かかる時間とアルゴリズムによって実行される基本操作の数は、定数係数によって関連していると見なされます。

アルゴリズムの実行時間は、同じサイズの異なる入力間で異なる場合があるため、通常は、最悪ケースの時間計算量、つまり、特定のサイズの入力に必要な最大時間が考慮されます。それほど一般的ではなく、通常は明示的に指定されるのが、平均ケースの計算量、つまり、特定のサイズの入力にかかる時間の平均です (特定のサイズの可能な入力の数は有限であるため、これは理にかなっています)。どちらの場合も、時間計算量は通常、入力のサイズの関数として表現されます。 ^{[1] : 226}この関数は正確に計算するのが一般的に難しく、小さな入力の実行時間は通常重要ではないため、入力サイズが増加したときの計算量の挙動、つまり、計算量の漸近的な挙動に一般的に焦点が当てられます。したがって、時間計算量は通常、big O 記法、つまり、、などを使用して表現されます。ここで、n は、入力を表すために必要な ビット単位でのサイズです。${\displaystyle O(n)}$ ${\displaystyle O(n\log n)}$ ${\displaystyle O(n^{\alpha })}$ ${\displaystyle O(2^{n})}$

アルゴリズムの複雑さは、ビッグ O 表記法で表示される関数の種類によって分類されます。たとえば、時間計算量のあるアルゴリズムは線形時間アルゴリズムであり、ある定数に対する時間計算量のあるアルゴリズムは多項式時間アルゴリズムです。 ${\displaystyle O(n)}$${\displaystyle O(n^{\alpha })}$${\displaystyle \alpha >0}$

次の表は、一般的に遭遇する時間計算量のいくつかのクラスをまとめたものです。表では、poly( x ) = x ^{O (1)}、つまり xの多項式です。

アルゴリズムの複雑さの値が入力のサイズに依存しない値によって制限される場合、そのアルゴリズムは定数時間(時間とも表記される) であると言われます。たとえば、配列内の任意の 1 つの要素にアクセスする場合、その要素を見つけるには1 つの操作のみを実行する必要があるため、定数時間がかかります。同様に、昇順にソートされた配列で最小値を検索する場合、それは最初の要素です。ただし、順序付けられていない配列で最小値を検索する操作は、最小値を決定するために配列内の各要素をスキャンする必要があるため、定数時間ではありません。したがって、これは線形時間操作であり、時間がかかります。ただし、要素の数が事前にわかっていて変更されない場合、そのようなアルゴリズムは定数時間で実行されると言えます。 ${\textstyle O(1)}$${\textstyle T(n)}$${\textstyle O(n)}$

「定数時間」という名前にもかかわらず、実行時間は問題のサイズに依存しない必要はありませんが、実行時間の上限は問題のサイズに依存しません。たとえば、「必要に応じてaとbの値を交換して、 」というタスクは、 がすでに真であるかどうかによって時間が左右される場合でも、定数時間と呼ばれます。ただし、必要な時間は常に最大でtになる定数tが存在します。 ${\textstyle a\leq b}$${\textstyle a\leq b}$

アルゴリズムが のとき、対数時間がかかると言われます。と は定数乗数で関連しており、このような乗数はビッグ O 分類とは無関係であるため、対数時間アルゴリズムの標準的な使用法は、Tの式に現れる対数の底に関係なく です。 ${\displaystyle T(n)=O(\log n)}$${\displaystyle \log _{a}n}$${\displaystyle \log _{b}n}$${\displaystyle O(\log n)}$

対数時間を要するアルゴリズムは、バイナリツリーの操作やバイナリ検索を使用する場合によく見られます。

アルゴリズムは、 n が増加すると、演算数と入力サイズの比率が減少し、ゼロに近づくため、非常に効率的であると考えられます。サイズnの入力を読み取るのにかかる時間はnのオーダーであるため、入力のすべての要素にアクセスする必要があるアルゴリズムでは、対数的な時間はかかりません。 ${\displaystyle O(\log n)}$

対数時間の例として、辞書検索が挙げられます。n個の項目がアルファベット順に並べられた辞書 D を考えてみましょう。 に対して、定数時間で辞書のk番目の項目にアクセスできるとします。このk番目の項目を で表します。これらの仮定の下では、単語wが辞書にあるかどうかを調べるテストは対数時間で実行できます。 を考えます。ここで、 は床関数を表します。 の場合(つまり、単語wが辞書のちょうど真ん中にある場合)、これで完了です。そうでない場合 (つまり、単語wがアルファベット順で辞書全体の真ん中の単語よりも前に来る場合)、辞書の左半分 (つまり、前の半分) で同じ方法で検索を続け、正しい単語が見つかるまでこれを繰り返します。そうでない場合、つまり単語 w が真ん中の単語の後にある場合は、辞書の右半分で同様に続けます。このアルゴリズムは、紙の辞書で項目を見つけるためによく使用される方法に似ています。その結果、アルゴリズムがターゲット単語に近づくにつれて、辞書内の検索スペースは減少します。 ${\displaystyle 1\leq k\leq n}$${\displaystyle D(k)}$${\displaystyle D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}$${\displaystyle \lfloor \;\rfloor }$${\displaystyle w=D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}$${\displaystyle w<D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}$

アルゴリズムの実行時間がある定数kにかかる場合、そのアルゴリズムは多重対数時間で実行されると言われます。これは と書くこともできます。 ${\displaystyle T(n)}$${\displaystyle O{\bigl (}(\log n)^{k}{\bigr )}}$${\displaystyle O(\log ^{k}n)}$

例えば、行列連鎖順序付けは並列ランダムアクセスマシン上で多重対数時間で解くことができ、^[7]挿入/削除操作ごとに完全に動的な方法でグラフが平面であることを決定できます。 ^[8]${\displaystyle O(\log ^{3}n)}$

アルゴリズムがサブ線形時間（サブ線形時間と表記されることが多い）で実行されるとされるのは、次の場合です。特に、これには上記で定義した時間計算量を持つアルゴリズムが含まれます。 ${\displaystyle T(n)=o(n)}$

サブ線形時間アルゴリズムという用語は、一般的に、入力のごく一部をサンプリングし、それを効率的に処理してインスタンス全体のプロパティを近似的に推測するランダム化アルゴリズムを指します。 ^{[9]このタイプのサブ線形時間アルゴリズムは、}プロパティテストと統計に密接に関連しています。

アルゴリズムをサブリニア時間で実行できるその他の設定は次のとおりです。

• 総作業量が線形以上（入力全体を読み取ることができる）だが、深さが線形未満の並列アルゴリズム。
• 入力構造に関する仮定が保証されているアルゴリズム。重要な例としては、ソートされた配列でのバイナリ検索など、データ構造に対する操作が挙げられます。
• 入力のローカル構造を検索するアルゴリズム。たとえば、1次元配列のローカル最小値を見つけるアルゴリズム（ バイナリ検索のバリエーションを使用して時間内に解決できます）。密接に関連する概念は、ローカル計算アルゴリズム（LCA）であり、アルゴリズムは大きな入力を受け取り、いくつかの有効な大きな出力に関するローカル情報を照会します。^[10]${\displaystyle O(\log(n))}$

アルゴリズムの時間計算量が の場合、そのアルゴリズムは線形時間または時間 かかると言われます。非公式には、これは実行時間が入力のサイズに最大でも線形に増加することを意味します。より正確には、これは、サイズnのすべての入力に対して実行時間が最大でも となる定数cが存在することを意味します。たとえば、リストのすべての要素を加算する手順では、加算時間が一定であるか、少なくとも定数で制限されている場合、リストの長さに比例した時間がかかります。 ${\displaystyle O(n)}$${\displaystyle O(n)}$${\displaystyle cn}$

線形時間は、アルゴリズムが入力全体を順番に読み取らなければならない状況で考えられる最良の時間計算量です。したがって、線形時間、または少なくともほぼ線形時間を示すアルゴリズムを発見するために多くの研究が行われてきました。この研究には、ソフトウェアとハ​​ードウェアの両方の手法が含まれます。並列処理を利用してこれを実現するハードウェア技術はいくつかあります。例としては、連想メモリがあります。この線形時間の概念は、ボイヤー・ムーア文字列検索アルゴリズムやウッコネンのアルゴリズムなどの文字列マッチングアルゴリズムで使用されています。

アルゴリズムは、ある正の定数kに対して であるとき、準線形時間（対数線形時間とも呼ばれる）で実行されると言われます。^[11]線形時間は の場合です。^[12]ソフト O 表記を使用すると、これらのアルゴリズムは です。準線形時間アルゴリズムは、すべての定数に対して であるため、任意の に対する項を含む時間境界を持つ多項式時間アルゴリズムよりも高速に実行されます。 ${\displaystyle T(n)=O(n\log ^{k}n)}$ ${\displaystyle k=1}$${\displaystyle {\tilde {O}}(n)}$${\displaystyle O(n^{1+\varepsilon })}$${\displaystyle \varepsilon >0}$${\displaystyle n^{c}}$${\displaystyle c>1}$

準線形時間で実行されるアルゴリズムには次のものがあります。

• インプレースマージソート、${\displaystyle O(n\log ^{2}n)}$
• クイックソートのランダム化バージョンでは、最悪のケースの入力に対して期待される実行時間になります。ランダム化されていないバージョンでは、平均的なケースの複雑さを考慮した場合のみ実行時間になります。${\displaystyle O(n\log n)}$${\displaystyle O(n\log n)}$${\displaystyle O(n\log n)}$
• ヒープソート、マージソート、イントロソート、バイナリツリーソート、スムースソート、ペイシエントソートなど、最悪の場合${\displaystyle O(n\log n)}$
• 高速フーリエ変換、${\displaystyle O(n\log n)}$
• モンジュ配列計算、${\displaystyle O(n\log n)}$

多くの場合、実行時間は単に操作をn回実行した結果です(表記法については、Big O 表記法 § バッハマン・ランダウ表記法のファミリーを参照してください)。たとえば、バイナリ ツリー ソートは、nサイズの配列の各要素を 1 つずつ挿入することでバイナリ ツリーを作成します。自己バランス型バイナリ サーチ ツリーでの挿入操作には時間がかかるため、アルゴリズム全体に時間がかかります。 ${\displaystyle O(n\log n)}$${\displaystyle \Theta (\log n)}$${\displaystyle O(\log n)}$${\displaystyle O(n\log n)}$

比較ソートでは、最悪の場合でも少なくとも 回の比較が必要になります。これは、スターリングの近似により となるためです。また、再帰関係からも頻繁に発生します。 ${\displaystyle \Omega (n\log n)}$${\displaystyle \log(n!)=\Theta (n\log n)}$ ${\textstyle T(n)=2T\left({\frac {n}{2}}\right)+O(n)}$

アルゴリズムがサブ2乗時間であるとは、次の場合を指します。 ${\displaystyle T(n)=o(n^{2})}$

たとえば、単純な比較ベースのソート アルゴリズムは 2 次式 (挿入ソートなど) ですが、より高度なアルゴリズムには準 2 次式 (シェルソートなど)もあります。汎用ソートは線形時間で実行されませんが、2 次式から準 2 次式への変更は実用上非常に重要です。

アルゴリズムの実行時間がアルゴリズムの入力のサイズの多項式式によって上限が定められている場合、つまり、ある正の定数kに対してT ( n ) = O ( n ^k )である場合、アルゴリズムは多項式時間であると言われる。^{[1] [13]}決定論的多項式時間アルゴリズムが存在する問題は、計算複雑性理論の分野で中心的なクラスPに属する。コブハムの論文では、多項式時間は「扱いやすい」、「実行可能」、「効率的」、「高速」の同義語であると述べられている。^[14]

多項式時間アルゴリズムの例をいくつか示します。

• n個の整数に対する選択ソート アルゴリズムは、定数Aに対して演算を実行します。したがって、このアルゴリズムは時間内に実行され、多項式時間アルゴリズムです。${\displaystyle An^{2}}$${\displaystyle O(n^{2})}$
• すべての基本的な算術演算 (加算、減算、乗算、除算、比較) は多項式時間で実行できます。
• グラフの最大マッチングは多項式時間で見つけることができます。特に最適化の分野では、強い多項式時間アルゴリズムと弱い多項式時間アルゴリズムを区別します。

これら 2 つの概念は、アルゴリズムへの入力が整数で構成されている場合にのみ関連します。

多項式時間の概念は、計算複雑性理論におけるいくつかの複雑性クラスにつながります。多項式時間を使用して定義される重要なクラスには次のようなものがあります。

• P :決定論的チューリングマシンで多項式時間で解ける決定問題の複雑さのクラス
• NP :非決定性チューリングマシンで多項式時間で解ける決定問題の複雑さのクラス
• ZPP :確率的チューリングマシンで多項式時間内にエラーゼロで解くことができる決定問題の複雑さのクラス
• RP : 確率的チューリングマシンで片側誤差で多項式時間で解決できる決定問題の複雑性クラス。
• BPP : 確率的チューリングマシンで多項式時間で両側誤差で解ける決定問題の複雑さのクラス
• BQP :量子チューリングマシンで多項式時間内に両側誤差で解くことができる決定問題の複雑さのクラス

P は、マシン モデルの変更に対して堅牢な決定論的マシン上の最小の時間複雑度クラスです。(たとえば、単一テープ チューリング マシンから複数テープ マシンへの変更は、2 乗の速度向上につながりますが、1 つのモデルで多項式時間で実行されるアルゴリズムは、他のモデルでも多項式時間で実行されます。) 任意の抽象マシンには、そのマシンで多項式時間で解決できる問題に対応する複雑度クラスがあります。

T ( n ) がどの多項式によっても上方に制限されない場合、アルゴリズムは超多項式時間を要すると定義されます。小さなオメガ記法を使用すると、すべての定数cに対してω ( n ^c ) 時間になります。ここで、n は入力パラメータであり、通常は入力のビット数です。

たとえば、サイズnの入力に対して2 ⁿステップ実行されるアルゴリズムには、超多項式時間 (より具体的には、指数時間) が必要です。

指数リソースを使用するアルゴリズムは明らかに超多項式ですが、一部のアルゴリズムは非常に弱い超多項式にすぎません。たとえば、Adleman–Pomerance–Rumely 素数判定は、nビットの入力に対してn ^{O (log log n )}時間で実行されます。これは、十分に大きいnに対してどの多項式よりも速く増加しますが、入力サイズが非実用的に大きくなるまで、次数の小さい多項式によって支配されなくなります。

超多項式時間を必要とするアルゴリズムは、複雑性クラス P の範囲外です。コブハムの論文では、これらのアルゴリズムは非実用的であるとしており、多くの場合、実際そうなっています。P対 NP 問題は未解決であるため、 NP 完全問題に超多項式時間が必要であるかどうかは不明です。

準多項式時間アルゴリズムは、実行時間が準多項式増加を示すアルゴリズムです。これは、多項式時間よりは遅くなるかもしれませんが、指数時間よりは大幅に高速なタイプの動作です。準多項式時間アルゴリズムの最悪ケースの実行時間は、ある固定値の に対してです。この場合、多項式時間となり、 の場合は線形以下の時間となります。 ${\displaystyle 2^{O(\log ^{c}n)}}$${\displaystyle c>0}$${\displaystyle c=1}$${\displaystyle c<1}$

準多項式時間アルゴリズムはわかっているが、多項式時間アルゴリズムはわかっていない問題がいくつかあります。このような問題は近似アルゴリズムで発生します。有名な例は有向シュタイナー木問題で、この問題には近似係数( nは頂点の数) を達成する準多項式時間近似アルゴリズムがありますが、そのような多項式時間アルゴリズムの存在を示すことは未解決の問題です。 ${\displaystyle O(\log ^{3}n)}$

準多項式時間で解けるが多項式時間で解けることが知られていない計算問題には、クリークとランダムグラフの和集合から大きなクリークを見つけることを目的とする植え付けクリーク問題がある。植え付けクリーク問題は準多項式的に解けるものの、多項式時間で解けないと予想されてきた。この植え付けクリーク予想は、計算ゲーム理論、プロパティテスト、機械学習における他のいくつかの問題の難しさを証明するための計算困難性仮定として使われてきた。^[15]

複雑性クラスQPは、準多項式時間アルゴリズムを持つすべての問題から構成されます。これは、 DTIMEの観点から次のように定義できます。^[16]

${\displaystyle {\mbox{QP}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}\left(2^{\log ^{c}n}\right)}$

複雑性理論では、未解決のP 対 NP問題は、NP のすべての問題に多項式時間アルゴリズムがあるかどうかを問うものです。3SAT などのNP 完全問題に対する最もよく知られているアルゴリズムはすべて指数時間がかかります。実際、多くの自然な NP 完全問題には、指数時間未満のアルゴリズムがないと推測されています。ここで「指数時間未満」とは、以下に示す 2 番目の定義を意味します。(一方、隣接行列によって自然な方法で表される多くのグラフ問題は、入力のサイズが頂点の数の 2 乗であるという理由だけで、指数時間未満で解決できます。) この推測 (k-SAT 問題の場合) は、指数時間仮説として知られています。^[17] NP完全問題には準多項式時間アルゴリズムがないと推測されているため、近似アルゴリズムの分野におけるいくつかの近似不可能性の結果は、NP完全問題には準多項式時間アルゴリズムがないという仮定を立てています。たとえば、集合被覆問題に対する既知の近似不可能性の結果を参照してください。

指数関数的時間という用語は、あるアルゴリズムの実行時間が多項式よりも速く増加する可能性があるが、それでも指数関数的時間より大幅に短いことを表すために使用されます。この意味で、指数関数的時間アルゴリズムがサブである問題は、指数アルゴリズムのみを持つ問題よりもいくらか扱いやすいです。「指数関数的」の正確な定義は一般的に合意されていませんが、^[18]最も広く使用されている 2 つを以下に示します。

問題が指数時間未満で解けるとは、対数が与えられた多項式よりも小さくなる実行時間で解けることを意味する。より正確には、すべてのε > 0に対して、問題をO (2 ^{n ε} )の時間で解くアルゴリズムが存在する場合、問題は指数時間未満である。このような問題の集合は複雑性クラスSUBEXPであり、これはDTIMEの観点から次のように定義できる。^{[6] [19] [20] [21]}

${\displaystyle {\text{SUBEXP}}=\bigcap _{\varepsilon >0}{\text{DTIME}}\left(2^{n^{\varepsilon }}\right)}$

このサブ指数の概念は、 εが入力の一部ではなく、各 ε が問題に対して独自のアルゴリズムを持つ可能性がある という意味で、 εに関して非均一です。

一部の著者は、指数関数的時間未満を で実行される時間と定義しています。^{[17] [22] [23]}この定義では、指数関数的時間の最初の定義よりも長い実行時間が許容されます。このような指数関数的時間未満アルゴリズムの例としては、整数因数分解の最もよく知られた古典的なアルゴリズムである一般数体ふるいが挙げられます。これは、入力の長さがnのとき、約 で実行されます。もう 1 つの例はグラフ同型性問題で、1982 年から 2016 年までの最もよく知られたアルゴリズムは でこれを解決しました。しかし、 STOC 2016では準多項式時間アルゴリズムが発表されました。^[24]${\displaystyle 2^{o(n)}}$${\displaystyle 2^{{\tilde {O}}(n^{1/3})}}$${\displaystyle 2^{O\left({\sqrt {n\log n}}\right)}}$

アルゴリズムがインスタンスのサイズ、頂点の数、または辺の数に対して指数関数的以下になることが許されるかどうかによって違いが生じます。パラメータ化された複雑性では、決定問題とパラメータkのペアを考慮することでこの違いが明確になります。SUBEPTは、 kに対して指数関数的以下で、入力サイズnに対して多項式の時間で実行されるすべてのパラメータ化された問題のクラスです。^[25]${\displaystyle (L,k)}$

${\displaystyle {\text{SUBEPT}}={\text{DTIME}}\left(2^{o(k)}\cdot {\text{poly}}(n)\right).}$

より正確には、SUBEPT は、 の計算可能な関数と、時間内にL を決定するアルゴリズムが存在するすべてのパラメーター化された問題のクラスです。 ${\displaystyle (L,k)}$ ${\displaystyle f:\mathbb {N} \to \mathbb {N} }$${\displaystyle f\in o(k)}$${\displaystyle 2^{f(k)}\cdot {\text{poly}}(n)}$

指数時間仮説( ETH ) は、3SAT、つまり、節ごとに最大 3 つのリテラルとn 個の変数を持つ連言正規形のブール式の充足可能性問題は、 2 ^{o ( n )}時間で解くことができないというものである。より正確には、この仮説は、 3SAT が任意の決定論的チューリングマシンによって2 ^cn時間で決定できないような絶対定数c > 0が存在するというものである。 mは節の数を表すので、 ETH は、任意の整数k ≥ 3に対してk SAT が 2 ^{o ( m )}時間で解くことができないという仮説と同等である。^[26]指数時間仮説は、P ≠ NP を意味する。

T ( n ) が 2 ^{poly( n )}で上限が定められている場合、アルゴリズムは指数時間であると言われます。ここで、 poly( n ) はn内の何らかの多項式です。より正式には、 T ( n ) が何らかの定数kに対してO (2 ^{n k} )で上限が定められている場合、アルゴリズムは指数時間です。決定論的チューリングマシン上で指数時間アルゴリズムを許容する問題は、 EXPとして知られる複雑性クラスを形成します。

${\displaystyle {\text{EXP}}=\bigcup _{c\in \mathbb {R_{+}} }{\text{DTIME}}\left(2^{n^{c}}\right)}$

指数時間は、 T ( n ) = 2 ^{O ( n )}（指数は最大でもnの線形関数）となるアルゴリズムを指すために使用されることがあります。これにより、複雑性クラスEが生じます。

${\displaystyle {\text{E}}=\bigcup _{c\in \mathbb {N} }{\text{DTIME}}\left(2^{cn}\right)}$

T(n)が階乗関数n!によって上限が定められている場合、アルゴリズムは階乗時間であると言われます。階乗時間は、すべての に対して であるため、指数時間 (EXP) のサブセットです。ただし、E のサブセットではありません。 ${\displaystyle n!\leq n^{n}=2^{n\log n}=O\left(2^{n^{1+\epsilon }}\right)}$${\displaystyle \epsilon >0}$

階乗時間で実行されるアルゴリズムの例としては、試行錯誤に基づく、効率の悪いソート アルゴリズムとして悪名高いbogosortがあります。bogosort は、 n個の項目のリストを繰り返しシャッフルして、ソートされたと判断されるまでリストをソートします。平均的なケースでは、bogosort アルゴリズムの各パスで、 n個の項目のn ! 個の順序の 1 つが調べられます。項目が別個である場合、そのような順序の 1 つだけがソートされます。bogosort は、無限の猿の定理と共通の遺産を持っています。

T ( n ) が 2 ^{2 poly( n )}で上限となる場合、アルゴリズムは二重指数時間であると言われます。ここで、 poly( n ) はn内の何らかの多項式です。このようなアルゴリズムは、複雑性クラス2-EXPTIMEに属します。

${\displaystyle {\mbox{2-EXPTIME}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}\left(2^{2^{n^{c}}}\right)}$

よく知られている二重指数時間アルゴリズムには以下のものがあります。

• プレスブルガー算術の決定手順
• グレブナー基底の計算（最悪の場合^[27]）
• 実閉体上の量指定子除去は少なくとも二重指数関数的時間がかかり^[28]、この時間内に実行できる。^[29]

• L表記
• 空間の複雑さ