Loading article…
理論計算機科学において、時間計算量とは、アルゴリズムの実行に必要なコンピュータ時間を表す計算複雑度です。時間計算量は、各基本操作の実行に一定の時間を要すると仮定し、アルゴリズムによって実行される基本操作の数を数えることで一般的に推定されます。したがって、アルゴリズムの実行時間と実行される基本操作の数は、定数倍の関係にあるとみなされます。
アルゴリズムの実行時間は、同じサイズの入力でも異なる場合があるため、一般的には最悪ケースの時間計算量、つまり特定のサイズの入力に必要な最大時間を考慮します。あまり一般的ではありませんが、通常は明示的に指定されるのが平均ケースの時間計算量です。これは、特定のサイズの入力にかかる時間の平均です（特定のサイズの入力は有限個しかないため、これは理にかなっています）。どちらの場合も、時間計算量は一般的に入力サイズの関数として表されます。 [ 1 ] : 226この関数は一般的に正確に計算するのが難しく、小さな入力の実行時間は通常重要ではないため、一般的には入力サイズが増加するときの計算量の挙動、つまり計算量の漸近的な挙動に注目します。したがって、時間計算量は一般的にビッグオー記法で表され、通常は、、、など。ここで、nは入力を表すために必要なビット単位のサイズです。
アルゴリズムの複雑さは、ビッグオー記法に現れる関数の種類に応じて分類されます。たとえば、時間計算量が のアルゴリズムは、は線形時間アルゴリズムであり、時間計算量を持つアルゴリズムである。ある定数に対してこれは多項式時間アルゴリズムです。
次の表は、よく遭遇する時間計算量のいくつかのクラスをまとめたものです。表では、poly( x ) = x O (1)、つまりxの多項式です。
アルゴリズムは定数時間（多くの場合、次のように表される）と呼ばれます。時間）その複雑性関数処理時間は、入力データのサイズに関係なく一定値に制限されます。これは、処理されるデータ量に関わらず、実行時間が一定であることを意味します。例えば、配列内の特定の要素にアクセスする操作は、その要素を見つけるのに必要な操作が1回だけなので、定数時間操作となります。
対照的に、順序付けされていない配列の最小値を決定するのは定数時間ではなく、各要素を調べる必要があるため、線形時間計算量、またはしかし、要素数が既知で固定されている場合は、特定のタスクは依然として定数時間とみなすことができます。
重要なのは、「定数時間」という用語は、実行時間が問題のサイズと完全に独立している必要があるという意味ではなく、入力サイズに関係なく一貫した上限を持つ必要があるという意味であるということです。たとえば、aとbの値を交換して、実行時間は条件が満たされているかどうかによって変動する可能性がある場合でも、これは定数時間として分類されます。重要なのは、入力値に関係なく、実行時間がt を超えることのない定数tが存在することです。
定数時間アルゴリズムは、実行時間の変動を悪用するタイミング攻撃が可能な暗号化などの分野において特に重要です。定数時間で実行されるアルゴリズムを設計することで、開発者はセキュリティを強化し、パフォーマンスの予測可能性を確保できるため、ソフトウェアエンジニアリングにおける基本的な考慮事項となっています。
アルゴリズムが対数時間かかるというのは、。 以来そしてこれらは定数倍数で関連付けられており、そのような倍数はビッグオー分類とは無関係であるため、対数時間アルゴリズムの標準的な使用法はTの式に現れる対数の底に関係なく。
対数時間を要するアルゴリズムは、二分木に対する操作や二分探索を用いる際によく見られる。
1アルゴリズムは、 n が増加するにつれて操作数と入力サイズの比率が減少し、ゼロに近づくため、非常に効率的であると考えられます。入力のすべての要素にアクセスする必要があるアルゴリズムは、対数時間で実行することはできません。サイズnの入力を読み取るのにかかる時間は、nのオーダーになります。
対数時間の例として、辞書検索が挙げられます。n個のエントリがアルファベット順にソートされた辞書Dを考えます。 の場合、定数時間で辞書のk番目のエントリにアクセスできる。これをk番目のエントリとします。これらの仮定の下では、単語wが辞書に含まれているかどうかのテストは対数時間で実行できます。、 どこは床関数を表します。つまり、単語wが辞書のちょうど真ん中にある場合、これで完了です。そうでなければ、つまり、単語w が辞書全体の真ん中の単語よりもアルファベット順で前に来る場合、辞書の左側（つまり、前の方）で同じように検索を続け、正しい単語が見つかるまでこれを繰り返します。そうでない場合、つまり真ん中の単語より後に来る場合は、辞書の右側で同様に検索を続けます。このアルゴリズムは、紙の辞書で項目を探す際によく使われる方法と似ています。結果として、アルゴリズムが目的の単語に近づくにつれて、辞書内の検索範囲は狭まります。
アルゴリズムの実行時間が多対数時間である場合、そのアルゴリズムは多対数時間で実行されると言われます。はある定数kに対して。これを別の方法で書くと次のようになります。。
例えば、行列連鎖順序付けは並列ランダムアクセスマシン上で多対数時間で解くことができ、[ 7 ]グラフは完全に動的な方法で平面であると判定できます。挿入/削除操作あたりの時間。[ 8 ]
アルゴリズムは、以下の条件を満たす場合に、準線形時間（しばしば「準線形時間」と綴られる）で実行されると言われます。特に、これには上記で定義された時間計算量を持つアルゴリズムが含まれます。
サブリニア時間アルゴリズムという用語は、入力のごく一部をサンプリングし、それを効率的に処理してインスタンス全体の特性を近似的に推測するランダム化アルゴリズムを指すのが一般的です。 [ 9 ]この種のサブリニア時間アルゴリズムは、特性テストと統計学に密接に関連しています。
アルゴリズムが準線形時間で実行できるその他の環境には、以下のようなものがあります。
アルゴリズムは線形時間で動作すると言われ、時間計算量が非公式には、これは実行時間が入力サイズに対して最大で線形に増加することを意味します。より正確には、これは実行時間が最大でサイズnのすべての入力に対して。たとえば、リストのすべての要素を合計する手順は、追加時間が一定であるか、少なくとも定数で制限されている場合、リストの長さに比例する時間を必要とします。
線形時間は、アルゴリズムが入力全体を順次読み込む必要がある状況において、可能な限り最良の時間計算量です。そのため、線形時間、あるいは少なくともほぼ線形時間を示すアルゴリズムの発見に多くの研究が費やされてきました。この研究には、ソフトウェアとハードウェアの両方の手法が含まれます。並列性を利用してこれを実現するハードウェア技術はいくつかあります。例えば、コンテンツアドレス指定可能なメモリが挙げられます。この線形時間の概念は、 Boyer–Moore文字列検索アルゴリズムやUkkonenアルゴリズムなどの文字列照合アルゴリズムで使用されています。
アルゴリズムは、以下の条件を満たす場合に準線形時間（対数線形時間とも呼ばれる）で実行されると言われます。ある正の定数kに対して、[ 11 ]線形時間の場合[ 12 ]ソフトO表記法を用いると、これらのアルゴリズムは次のようになる。準線形時間アルゴリズムもまたすべての定数に対してそのため、時間制限に項が含まれる多項式時間アルゴリズムよりも高速に実行されます。いかなる場合でも。
準線形時間で実行されるアルゴリズムには、以下のようなものがある。
多くの場合、実行時間は単に実行の結果です操作をn回実行します (表記については、ビッグ O 表記 § バッハマン・ランダウ表記のファミリーを参照)。たとえば、バイナリツリーソートは、nサイズの配列の各要素を 1 つずつ挿入してバイナリツリーを作成します。自己平衡バイナリ探索ツリーへの挿入操作は、時間、アルゴリズム全体には時間。
比較ソートには少なくとも最悪の場合の比較はスターリングの近似式による。また、それらはしばしば漸化式から生じる。。
アルゴリズムが準二次時間であるとは、。
例えば、単純な比較ベースのソートアルゴリズムは2次計算量（挿入ソートなど）ですが、より高度なアルゴリズムの中には2次未満の計算量（シェルソートなど）を持つものもあります。汎用的なソートアルゴリズムで線形時間で実行できるものはありませんが、2次から2次未満の計算量への変化は、実用上非常に重要です。
アルゴリズムの実行時間が、そのアルゴリズムへの入力のサイズに関する多項式表現で上限が定められている場合、そのアルゴリズムは多項式時間であると言われます。つまり、ある正の定数kに対してT ( n ) = O ( n k )となります。[ 1 ] [ 13 ]決定論的な多項式時間アルゴリズムが存在する問題は、計算複雑性理論の分野で中心的な役割を果たす複雑性クラスPに属します。コブハムのテーゼでは、多項式時間は「扱いやすい」、「実行可能」、「効率的」、または「高速」の同義語であると述べられています。[ 14 ]
多項式時間アルゴリズムの例をいくつか挙げます。
これら2つの概念は、アルゴリズムへの入力が整数である場合にのみ関連性を持つ。
多項式時間の概念は、計算複雑性理論におけるいくつかの複雑性クラスにつながります。多項式時間を用いて定義される重要なクラスには、以下のようなものがあります。
P は、マシンモデルの変更に対して堅牢な、決定論的マシン上の最小の時間計算量クラスです。（例えば、シングルテープチューリングマシンからマルチテープマシンへの変更は、2 乗の速度向上につながる可能性がありますが、一方のモデルで多項式時間で実行されるアルゴリズムは、もう一方のモデルでも同様に実行されます。）任意の抽象マシンには、そのマシン上で多項式時間で解決できる問題に対応する計算量クラスが存在します。
T ( n )がどの多項式によっても上から抑えられない場合、すなわち、すべての正の整数cに対して。
例えば、入力サイズがnの場合に2 nステップ実行されるアルゴリズムは、超多項式時間（より正確には指数時間）を必要とします。
指数関数的なリソースを使用するアルゴリズムは明らかに超多項式ですが、超多項式であるのはごく弱いアルゴリズムだけです。たとえば、Adleman–Pomerance–Rumely素数判定法は、nビット入力に対してn O (log log n )の時間で実行されます。これは、 nが十分に大きい場合、どの多項式よりも速く増加しますが、入力サイズが非現実的なほど大きくなれば、小さな次数を持つ多項式で支配できなくなります。
超多項式時間を必要とするアルゴリズムは、複雑性クラスPの範囲外にある。コブハムの論文では、これらのアルゴリズムは実用的ではないと主張されており、多くの場合、その通りである。P対NP問題は未解決であるため、NP完全問題が超多項式時間を必要とするかどうかは不明である。
準多項式時間アルゴリズムとは、実行時間が準多項式的に増加するアルゴリズムのことです。準多項式時間アルゴリズムは、多項式時間よりは遅いものの、指数時間よりははるかに速い動作を示します。準多項式時間アルゴリズムの最悪実行時間はある固定値に対して。いつこれにより多項式時間が得られ、それは準線形時間を与える。
準多項式時間アルゴリズムは知られているが、多項式時間アルゴリズムは知られていない問題がいくつか存在する。このような問題は近似アルゴリズムで発生する。有名な例として、有向シュタイナー木問題があり、この問題に対しては、近似係数 を達成する準多項式時間近似アルゴリズムが存在する。（nは頂点の数）であるが、そのような多項式時間アルゴリズムの存在を示すことは未解決問題である。
準多項式時間解法は存在するが、既知の多項式時間解法が存在しない他の計算問題には、クリークとランダムグラフの和集合から大きなクリークを見つけることを目的とする、植え付けクリーク問題がある。準多項式時間で解けるにもかかわらず、植え付けクリーク問題には多項式時間解法が存在しないと推測されている。この植え付けクリーク予想は、計算ゲーム理論、特性テスト、機械学習における他のいくつかの問題の難しさを証明するための計算困難性の仮定として用いられてきた。[ 15 ]
複雑性クラスQPは、準多項式時間アルゴリズムを持つすべての問題から構成されます。DTIMEの観点からは、次のように定義できます。[ 16 ]
計算複雑性理論において、未解決の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 ]
この準指数関数の概念は、 εに関して非一様である。なぜなら、εは入力の一部ではなく、それぞれのεに対して問題に対する独自のアルゴリズムが存在する可能性があるからである。
一部の著者は、サブ指数時間を、実行時間として定義しています。[ 17 ] [ 22 ] [ 23 ]この定義では、最初の準指数時間の定義よりも長い実行時間が許容されます。このような準指数時間アルゴリズムの例として、整数因数分解のための最もよく知られた古典的なアルゴリズムである一般数体篩法があり、これは約 の時間で実行されます。ここで、入力の長さはnである。別の例としては、グラフ同型性問題があり、1982年から2016年までの最もよく知られたアルゴリズムは、しかし、STOC 2016では準多項式時間アルゴリズムが発表された。[ 24 ]
アルゴリズムがインスタンスのサイズ、頂点の数、またはエッジの数に対して準指数関数的であるかどうかは、違いを生みます。パラメータ化された複雑性では、この違いはペアを考慮することによって明確になります。決定問題とパラメータkのクラスSUBEPTは、kに対して準指数時間、入力サイズnに対して多項式時間で実行されるすべてのパラメータ化された問題のクラスです。[ 25 ]
より正確には、SUBEPTはすべてのパラメータ化された問題のクラスである。計算可能な関数が存在するとそして、 Lを時間内に決定するアルゴリズム。
指数時間仮説（ETH）は、節ごとに最大 3 つのリテラルとn 個の変数を持つ連言標準形のブール式の充足可能性問題である3SAT は、2 o ( n )の時間で解くことができないというものです。より正確には、この仮説は、3SAT を任意の決定性チューリング マシンで2 cn の時間で決定できないような絶対定数c > 0が存在するというものです。節の数をmとすると、ETH は、任意の整数k ≥ 3に対してk SAT を 2 o ( m )の時間で解くことができないという仮説と同等です。[ 26 ]指数時間仮説はP ≠ NP を意味します。
アルゴリズムは、T ( n ) がnに関する何らかの多項式poly( n )で上から抑えられる場合、指数時間であると言われます。より厳密には、アルゴリズムは、T ( n ) が定数kに対してO (2 n k )で抑えられる場合、指数時間であると言われます。決定性チューリングマシン上で指数時間アルゴリズムを許容する問題は、EXPとして知られる複雑性クラスを形成します。
指数時間という言葉は、 T ( n ) = 2O ( n )となるアルゴリズムを指す場合があり、指数はnの線形関数以下です。これにより、複雑性クラスEが生まれます。
アルゴリズムは、T(n)が階乗関数n!で上から抑えられる場合、階乗時間であると言われます。階乗時間は指数時間 (EXP) の部分集合です。すべての人々のためにしかし、それは E の部分集合ではありません。
階乗時間で実行されるアルゴリズムの例として、試行錯誤に基づく非効率的なソートアルゴリズムであるボゴソートがあります。ボゴソートは、n個の項目のリストがソートされるまで繰り返しシャッフルすることで、リストをソートします。平均的なケースでは、ボゴソートアルゴリズムの各パスで、 n 個の項目のn !通りの順序のうちの 1 つが調べられます。項目が互いに異なる場合、そのような順序のうち 1 つだけがソートされます。ボゴソートは、無限猿定理と共通の起源を持っています。
アルゴリズムの計算量がT ( n ) の上限が 2 2 poly( n )で抑えられる場合、そのアルゴリズムは二重指数時間であると言われます。ここで poly( n ) はnに関する何らかの多項式です。このようなアルゴリズムは、複雑性クラス2-EXPTIMEに属します。
よく知られている二重指数時間アルゴリズムには以下のようなものがある。
{{cite book}}: CS1 maint: 複数の名前: 著者リスト (リンク){{cite book}}: CS1メンテナンス: DOIは2025年7月現在非アクティブです（リンク）