時間計算量

理論計算機科学において、時間計算量とは、アルゴリズムの実行に必要なコンピュータ時間を表す計算複雑度です。時間計算量は、各基本操作の実行に一定の時間を要すると仮定し、アルゴリズムによって実行される基本操作の数を数えることで一般的に推定されます。したがって、アルゴリズムの実行時間と実行される基本操作の数は、定数倍の関係にあるとみなされます。

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

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

次の表は、よく遭遇する時間計算量のいくつかのクラスをまとめたものです。表では、${\displaystyle {\text{poly}}(x)=x^{O(1)}}$つまり、${\displaystyle x}$。

アルゴリズムは定数時間（多くの場合、次のように表される）と呼ばれます。${\displaystyle O(1)}$時間）その複雑性関数${\displaystyle T(n)}$処理時間は、入力データのサイズに関係なく一定値に制限されます。これは、処理されるデータ量に関わらず、実行時間が一定であることを意味します。例えば、配列内の特定の要素にアクセスする操作は、その要素を見つけるのに必要な操作が1回だけなので、定数時間操作となります。

対照的に、順序付けされていない配列の最小値を決定するのは定数時間ではなく、各要素を調べる必要があるため、線形時間計算量、または${\displaystyle O(n)}$しかし、要素数が既知で固定されている場合は、特定のタスクは依然として定数時間とみなすことができます。

重要なのは、「定数時間」という用語は、実行時間が問題のサイズと完全に独立している必要があるという意味ではなく、入力サイズに関係なく一貫した上限を持つ必要があるという意味であるということです。たとえば、値を交換するタスクでは、${\displaystyle a}$そして${\displaystyle b}$確実に${\displaystyle a\leq b}$実行時間は条件が既に満たされているかどうかによって変動する可能性がある場合でも、定数時間として分類されます。重要なのは定数が存在することです。${\displaystyle t}$所要時間が決して超えないように${\displaystyle t}$入力値に関係なく。

定数時間アルゴリズムは、実行時間の変動を悪用するタイミング攻撃が可能な暗号化などの分野において特に重要です。定数時間で実行されるアルゴリズムを設計することで、開発者はセキュリティを強化し、パフォーマンスの予測可能性を確保できるため、ソフトウェアエンジニアリングにおける基本的な考慮事項となっています。

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

対数時間を要するアルゴリズムは、二分木に対する操作や二分探索を用いる際によく見られる。

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

対数時間の例として、辞書検索が挙げられます。辞書を考えてみましょう。${\displaystyle D}$含まれる${\displaystyle n}$エントリはアルファベット順にソートされています。${\displaystyle 1\leq k\leq n}$アクセスできる${\displaystyle k}$辞書の 番目のエントリを定数時間で取得します。${\displaystyle D(k)}$これを示す${\displaystyle k}$- 番目のエントリ。これらの仮説の下では、単語が - 番目のエントリであるかどうかを確認するテストは、${\displaystyle w}$辞書にあるものは対数時間で実行できる可能性があります。${\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}$が辞書のちょうど真ん中にある場合、これで完了です。そうでない場合、${\displaystyle w<D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)}$つまり、単語が${\displaystyle w}$目的の単語が辞書全体の真ん中の単語よりもアルファベット順で前に来る場合は、辞書の左側（つまり、前の方）で同じように検索を続け、正しい単語が見つかるまで繰り返します。そうでない場合、目的の単語が真ん中の単語よりも後に来る場合は、辞書の右側で同様に検索を続けます。このアルゴリズムは、紙の辞書で項目を探す際によく使われる方法と似ています。結果として、アルゴリズムが目的の単語に近づくにつれて、辞書内の検索範囲は狭まります。

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

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

アルゴリズムは、以下の条件を満たす場合に、準線形時間（しばしば「準線形時間」と綴られる）で実行されると言われます。${\displaystyle T(n)=o(n)}$特に、これには上記で定義された時間計算量を持つアルゴリズムが含まれます。

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

アルゴリズムが準線形時間で実行できるその他の環境には、以下のようなものがあります。

• 総作業量が線形以上（入力全体を読み込むことができる）であるが、深さが線形未満の並列アルゴリズム。
• 入力構造に関する前提条件が保証されているアルゴリズム。重要な例としては、データ構造に対する操作、例えばソート済み配列における二分探索などが挙げられる。
• 入力内の局所構造を探索するアルゴリズム、例えば 1 次元配列内の局所最小値を見つけるアルゴリズムは、${\displaystyle O(\log(n))}$バイナリサーチの変種を使用した時間）。これと密接に関連する概念として、ローカル計算アルゴリズム（LCA）があり、アルゴリズムは大きな入力を受け取り、有効な大きな出力に関するローカル情報に問い合わせます。^{[ 10 ]}

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

線形時間は、アルゴリズムが入力全体を順次読み込む必要がある状況において、可能な限り最良の時間計算量です。そのため、線形時間、あるいは少なくともほぼ線形時間を示すアルゴリズムの発見に多くの研究が費やされてきました。この研究には、ソフトウェアとハ​​ードウェアの両方の手法が含まれます。並列性を利用してこれを実現するハードウェア技術はいくつかあります。例えば、コンテンツアドレス指定可能なメモリが挙げられます。この線形時間の概念は、 Boyer–Moore文字列検索アルゴリズムやUkkonenアルゴリズムなどの文字列照合アルゴリズムで使用されています。

アルゴリズムは、以下の条件を満たす場合に準線形時間（対数線形時間とも呼ばれる）で実行されると言われます。${\displaystyle T(n)=O(n\log ^{k}n)}$ある正の定数に対して${\displaystyle k}$; ^{[ 11 ]}線形時間の場合${\displaystyle k=1}$^{[ 12 ]}ソフトO表記法を用いると、これらのアルゴリズムは次のようになる。$\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)}$
• 乗算用のシェーンハーゲ・シュトラッセンアルゴリズム、${\displaystyle O(n\log n\log \log n)}$

多くの場合、${\displaystyle O(n\log n)}$実行時間は単に実行の結果です${\displaystyle \Theta (\log n)}$手術${\displaystyle n}$回（表記については、ビッグオー記法§ バッハマン・ランダウ記法のファミリーを参照）。たとえば、バイナリツリーソートは、バイナリツリーの各要素を挿入することによってバイナリツリーを作成します。${\displaystyle n}$サイズ配列を1つずつ挿入します。自己平衡二分探索木への挿入操作は${\displaystyle O(\log n)}$時間、アルゴリズム全体には${\displaystyle O(n\log n)}$時間。

比較ソートには少なくとも${\displaystyle \Omega (n\log n)}$最悪の場合の比較は${\displaystyle \log(n!)=\Theta (n\log n)}$スターリングの近似式による。また、それらはしばしば漸化式から生じる。${\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+O(n)}$。

アルゴリズムが準二次時間であるとは、${\displaystyle T(n)=o(n^{2})}$。

例えば、単純な比較ベースのソートアルゴリズムは2次計算量（挿入ソートなど）ですが、より高度なアルゴリズムの中には2次未満の計算量（シェルソートなど）を持つものもあります。汎用的なソートアルゴリズムで線形時間で実行できるものはありませんが、2次から2次未満の計算量への変化は、実用上非常に重要です。

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

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

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

これら2つの概念は、アルゴリズムへの入力が整数である場合にのみ関連性を持つ。

アルゴリズムが超多項式時間で実行されると定義されるのは、${\displaystyle T(n)}$はどの多項式によっても上から抑えられない。つまり、${\displaystyle T(n)\not \in O(n^{c})}$すべての正の整数に対して${\displaystyle c}$。

例えば、次のアルゴリズムを実行すると${\displaystyle 2^{n}}$サイズの入力に対するステップ${\displaystyle n}$超多項式時間（より具体的には指数時間）を必要とする。

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

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

準多項式時間アルゴリズムとは、実行時間が準多項式的に増加するアルゴリズムのことです。準多項式時間アルゴリズムは、多項式時間よりは遅いものの、指数時間よりははるかに速い動作を示します。準多項式時間アルゴリズムの最悪実行時間は${\displaystyle 2^{O(\log ^{c}n)}}$ある固定値に対して${\displaystyle c>0}$。 いつ${\displaystyle c=1}$これにより多項式時間が得られ、${\displaystyle c<1}$それは準線形時間を与える。

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

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

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

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

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

アルゴリズムは、以下の条件を満たす場合に指数時間であると言われます。${\displaystyle T(n)}$上限は${\displaystyle 2^{{\text{poly}}(n)}}$、 どこ${\displaystyle {\text{poly}}(n)}$は、ある多項式である。${\displaystyle n}$より厳密に言えば、アルゴリズムが指数時間であるのは、${\displaystyle T(n)}$境界は${\displaystyle O(2^{n^{k}})}$ある定数に対して${\displaystyle k}$決定性チューリングマシン上で指数時間アルゴリズムを許容する問題は、EXPと呼ばれる複雑性クラスを形成します。

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

指数時間という言葉は、次のようなアルゴリズムを指す場合に使われることがあります。${\displaystyle T(n)=2^{O(n)}}$、ここで指数は、の線形関数である。${\displaystyle n}$これにより、複雑性クラスEが生まれる。

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

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

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

アルゴリズムが二重指数時間であるとは、${\displaystyle T(n)}$上限は${\displaystyle 2^{2^{{\text{poly}}(n)}}}$、 どこ${\displaystyle {\text{poly}}(n)}$は、ある多項式である。${\displaystyle n}$このようなアルゴリズムは、複雑性クラス2-EXPTIMEに属します。

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

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

• プレスバーガー算術の決定手順
• グロブナー基底の計算（最悪の場合^{[ 27 ]}）
• 実閉体上の量化子消去には少なくとも2倍の指数時間が必要であり、^{[ 28 ]}この時間内に実行できる。^{[ 29 ]}

• L記法
• 空間の複雑さ