計算複雑性理論
(計算量 から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/04/28 16:32 UTC 版)
計算複雑性理論（けいさんふくざつせいりろん、英: computational complexity theory）とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性（計算問題の困難さ）などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。
- ^ a b c d Sipser, Michael (2006年). “Time Complexity”. Introduction to the Theory of Computation (2nd edition ed.). USA: Thomson Course Technology. ISBN 0-534-95097-3
- ^ Berger, Bonnie A.; Leighton, Terrance (1998年). “Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete.”. Journal of Computational Biology 5 (1): p27-40.、PubMed
- ^ Cook, Stephen (2000年4月) (PDF). The P versus NP Problem. クレイ数学研究所 2006年10月18日閲覧。.
- ^ Jaffe, Arthur M.. “The Millennium Grand Challenge in Mathematics” (PDF). Notices of the AMS 53 (6) 2006年10月18日閲覧。.
- ^ a b Du, Ding-Zhu; Ko, Ker-I (2000年). Theory of Computational Complexity. John Wiley & Sons. ISBN 978-0-471-34506-0
- 1 計算複雑性理論とは
- 2 計算複雑性理論の概要
- 3 決定問題
- 4 計算資源
- 5 イントラクタブル
- 6 外部リンク
計算量
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/12/11 07:56 UTC 版)
長きに渡って、単純多角形を O ( n log n ) {\displaystyle O(n\log n)} 時間より高速な三角形分割アルゴリズムが未発見であった。その後、Tarjan & Van Wyk (1988)は O ( n log log n ) {\displaystyle O(n\log \log n)} 時間で三角化を行うアルゴリズムを発見し、後にKirkpatrick Klaweとロバート・タージャンにより簡単化された。複数の改善により、 O ( n log ∗ n ) {\displaystyle O(n\log ^{\ast }n)} （実用上ほぼ線形時間）を実現している。 1991年にバーナード・チャゼルは非常な複雑なアルゴリズムではあるが、任意の単純多角形を線形時間で三角形分割するアルゴリズムを示した。また、乱択アルゴリズムを用いることで、平均計算時間が線形時間であるアルゴリズムも存在する。 ザイデルの分割アルゴリズムとチャゼルの三角形分割については、 Li & Klette (2011) が詳しい。 穴を持つn頂点の多角形の三角形分割の時間計算量の下界は Ω ( n log n ) {\displaystyle \Omega (n\log n)} 与えられている。
※この「計算量」の解説は、「多角形の三角形分割」の解説の一部です。
「計算量」を含む「多角形の三角形分割」の記事については、「多角形の三角形分割」の概要を参照ください。
計算量
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/28 00:24 UTC 版)
クラメルの法則を利用して n 元線型方程式系を解こうとすれば、n + 1 個の行列式を計算しなければならない。このアルゴリズムにおいて算術演算の数は専ら行列式の計算から生じる。 クラメルの法則に現れる行列式をライプニッツの公式に従って計算すれば、(n − 1)·n! 回の掛け算と n − 1 回の足し算をすることになる。これは4本の方程式を持つ系の場合でも、360回の掛け算、4回の割り算、115回の足し算をすることを意味する。これは他の方法に比べて極めて多くの計算を要する。行列式の計算により効率的なアルゴリズムを用いたとしても、線型方程式をクラメルの法則で解こうとすれば、ガウス消去法などよりもずっと大きな計算量が必要になる。 n 元一次連立方程式に対して、毎秒 108 回浮動小数点演算可能 (100 Mflops) な性能の計算機で計算すると、計算時間は次の表のようになる: n10 12 14 16 18 20 計算時間0.4秒 1分 3.6時間 41日 38年 16,000年
※この「計算量」の解説は、「クラメルの公式」の解説の一部です。
「計算量」を含む「クラメルの公式」の記事については、「クラメルの公式」の概要を参照ください。
計算量
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/29 06:54 UTC 版)
「ポラード・ロー離散対数アルゴリズム」の記事における「計算量」の解説
実行時間はおよそ O ( n ) {\displaystyle {\mathcal {O}}({\sqrt {n}})} である。ポーリヒ・ヘルマンのアルゴリズム（英語: Pohlig-Hellman algorithm）と組み合わせた場合の実行時間は、pをnの最大の素因数としたとき O ( p ) {\displaystyle {\mathcal {O}}({\sqrt {p}})} である。
※この「計算量」の解説は、「ポラード・ロー離散対数アルゴリズム」の解説の一部です。
「計算量」を含む「ポラード・ロー離散対数アルゴリズム」の記事については、「ポラード・ロー離散対数アルゴリズム」の概要を参照ください。
計算量
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/30 15:36 UTC 版)
計算量は以下の通り。 オリジナル : O ( V 2 ) {\displaystyle O(V^{2})} 優先度付きキュー（二分ヒープ）: O ( ( E + V ) log V ) {\displaystyle O((E+V)\log {V})} 優先度付きキュー（フィボナッチヒープ）: O ( E + V log V ) {\displaystyle O(E+V\log {V})} 優先度付きキューを使用した場合の計算量としては、以下の合算である。下記説明は上記擬似コードに基づき、ループ回数も考慮に入れている。 「 Q ← V {\displaystyle Q\leftarrow V} 」：二分ヒープもフィボナッチヒープも O ( V ) {\displaystyle O(V)} 。ただし、二分ヒープは追加を V 回繰り返す実装にすると O ( V log V ) {\displaystyle O(V\log V)} 。 「 u ← d ( u ) {\displaystyle u\leftarrow d(u)} が最小である頂点 u ∈ Q {\displaystyle u\in Q} 」：二分ヒープもフィボナッチヒープも O ( V ) {\displaystyle O(V)} 「 Q {\displaystyle Q} から u {\displaystyle u} を取り除く」：二分ヒープもフィボナッチヒープも O ( V log V ) {\displaystyle O(V\log V)} 「 d ( v ) ← d ( u ) + length ( u , v ) {\displaystyle d(v)\leftarrow d(u)+{\text{length}}(u,v)} 」：二分ヒープは O ( E log V ) {\displaystyle O(E\log V)} 、フィボナッチヒープは O ( E ) {\displaystyle O(E)}
※この「計算量」の解説は、「ダイクストラ法」の解説の一部です。
「計算量」を含む「ダイクストラ法」の記事については、「ダイクストラ法」の概要を参照ください。
計算量
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/01 22:35 UTC 版)
「ユークリッドの互除法」の記事における「計算量」の解説
割って余りを取るという操作を、最悪でも小さいほうの十進法での桁数の約 5 倍繰り返せば、最大公約数に達する（ラメの定理）。 最大公約数を求めるのに、素因数分解すればよいと思うかもしれないが、この定理は（m, n が大きいときには）素因数分解をするよりもユークリッドの互除法によるほうがはるかに速いということを述べている。 実際、計算複雑性理論においては最大公約数を求めることは「容易な問題」として知られており、素因数分解は「困難な問題」であろうと考えられている。入力された2つの整数のうち小さいほうの整数 n の桁数を d とすれば、ユークリッドの互除法では O(d) 回の除算で最大公約数が求められる。桁数 d は O(log n) なので、ユークリッドの互除法では O(log n) 回の除算で最大公約数が求められる。
※この「計算量」の解説は、「ユークリッドの互除法」の解説の一部です。
「計算量」を含む「ユークリッドの互除法」の記事については、「ユークリッドの互除法」の概要を参照ください。
計算量
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/15 15:56 UTC 版)
辺の数をE、Vを頂点の数として、ブルーフカ法はO(log V)回の反復をするため、計算には時間O(E log V)かかる。平面グラフでは、反復するごとにふたつの木の間で重みが最小の辺以外を取り除くことにより、より線形に近い計算量で済む。
※この「計算量」の解説は、「ブルーフカ法」の解説の一部です。
「計算量」を含む「ブルーフカ法」の記事については、「ブルーフカ法」の概要を参照ください。
計算量
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/06/22 05:55 UTC 版)
入力列の個数が任意である一般の場合については、この問題はNP困難である。入力列の個数が一定のときには、この問題は動的計画法によって多項式時間で解く事ができる（後の項参照）。 N {\displaystyle N} 個の列があり、長さが n 1 , . . . , n N {\displaystyle n_{1},...,n_{N}} であるとする。単純な探索では、最初の列の 2 n 1 {\displaystyle 2^{n_{1}}} 個の部分列が残りの列の部分列であるかを確かめる。それぞれの配列は、残りの配列長の線形時間で評価される。それゆえ、このアルゴリズムの計算時間は、下記の通りである。 O ( 2 n 1 ∑ i > 1 n i ) . {\displaystyle O\left(2^{n_{1}}\sum _{i>1}n_{i}\right).} 2つの配列で列の長さが n と m の場合、動的計画法の解法による時間計算量は、O(n × m)である。入力配列の個数が任意の場合、動的計画法の解法は下記の計算量で解を与える。 O ( N ∏ i = 1 N n i ) . {\displaystyle O\left(N\prod _{i=1}^{N}n_{i}\right).} より計算量の小さい方法が存在するが、それはしばしば、最長共通部分列の配列長か、アルファベット(=対象とする列に現れる要素)のサイズ、もしくはその両方に依存する。 注意：最長共通部分列は、必ずしも一意ではない。例として ”ABC” と ”ACB” の最長共通部分列は ”AB” と ”AC” の両方である。実際、最長共通部分列の定義が「長さ最大の共通部分列をすべて見つけること」であることも多い。このように問題を変更すると、計算量は増大してしまう。なぜならば、長さ最大の部分列の数は最悪の場合、指数関数的に増大する。入力配列が2つの場合でさえ同様である。
※この「計算量」の解説は、「最長共通部分列問題」の解説の一部です。
「計算量」を含む「最長共通部分列問題」の記事については、「最長共通部分列問題」の概要を参照ください。
計算量
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/02/10 17:40 UTC 版)
「クワイン・マクラスキー法」の記事における「計算量」の解説
（主として人間の把握能力の限界により）4〜6変数程度以上の簡単化はカルノー図では不可能で、コンピュータ・プログラムによりクワイン・マクラスキー法を使うのが現実的となる。しかし、充足可能性問題であるためNP困難であることから、実行時間が入力長に対し指数関数的に増加するという問題がある。具体的には、n変数関数における主項の数の上限が3nとなるため例えば n = 32とおくと、主項の数は6.5 × 1015を超えることもある。そのため変数の多い関数の簡単化においては、最適解は保証されないが現実的な時間内で比較的良質な解を得られる、ヒューリスティックを含む方法に切り替えなければならない。
※この「計算量」の解説は、「クワイン・マクラスキー法」の解説の一部です。
「計算量」を含む「クワイン・マクラスキー法」の記事については、「クワイン・マクラスキー法」の概要を参照ください。
計算量
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/16 02:39 UTC 版)
DBSCAN はデータベースの各点を訪れる。複数回訪れることもある(たとえば、異なるクラスタへの候補として)。しかし、実践の考慮のため、時間計算量はたいてい regionQuery の呼び出しの回数によって支配される。DBSCAN は各点でそのようなクエリをまさに 1 度だけ実行し、O(log n) で近隣クエリ(en:Fixed-radius_near_neighbors)を実行するインデックス構造が使用されるならば、O(n log n) の全体平均のランタイム複雑性が獲得される(パラメータ ε が意味のある中で選ばれたならば。すなわち、平均して O(log n) の点が返される場合ならば)。加速させるようなインデックス構造を使用しない場合、または縮退データ(たとえばすべての点が ε より小さい距離内にある)の場合は、その最悪計算時間は O(n²) のままである。サイズ (n²-n)/2 の距離行列は距離の再計算を回避するために出現しうるが、これは O(n²) のメモリを必要とする。一方、DBSCAN の非行列に基づく実装はわずか O(n) のメモリを必要とする。
※この「計算量」の解説は、「DBSCAN」の解説の一部です。
「計算量」を含む「DBSCAN」の記事については、「DBSCAN」の概要を参照ください。
計算量
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/02/21 22:30 UTC 版)
計算量（最大ヒープ）操作最悪計算量償却計算量最大値の取得O(1) O(1) 要素数の取得O(1) O(1) 追加O(1) O(1) 削除Ω(n) O(log n) 値の更新Ω(n) O(1) 上記の償却計算量を最悪計算量にしたい場合は、弛緩ヒープ (英: relaxed heap) を用いると良い。
※この「計算量」の解説は、「フィボナッチヒープ」の解説の一部です。
「計算量」を含む「フィボナッチヒープ」の記事については、「フィボナッチヒープ」の概要を参照ください。
計算量
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/11/10 08:33 UTC 版)
入力されるリストの項目数 n に基づいた計算量による分類。典型的なソートアルゴリズムでは、最善で O(n log n) 、最悪で O(n2) である。理想は O(n) である。 比較ソートでは、必ず O(n log n) の比較が必要となる。（→#比較ソートの理論限界）
※この「計算量」の解説は、「ソート」の解説の一部です。
「計算量」を含む「ソート」の記事については、「ソート」の概要を参照ください。
計算量
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/28 15:48 UTC 版)
グラフ彩色は困難である。k = 1 および k = 2 以外の k について「与えられたグラフがk-彩色可能か」という決定問題はNP完全問題である。彩色数を求める問題はNP困難である。彩色可能性を問う決定問題は次数が最大4の平面グラフであってもNP完全である。 既知の最良の近似アルゴリズムはオーダー O(n(log n)−3(log log n)2) の近似精度で彩色数を計算する。あらゆる ε > 0 について、n1−ε 以内に彩色数を近似することはNP困難である。 3-彩色可能なグラフを4色で彩色する問題もNP困難であり、k-彩色可能なグラフを k(log k ) / 25 色で彩色する問題も k が十分大きければNP困難である。 彩色多項式の係数を求める問題は#P困難である。実際 k = 1 または k = 2 以外の任意の有理数 k について χ ( G , k ) {\displaystyle \chi (G,k)} を求める計算も#P困難である。NP = RP でない限り、k = 2 以外の k ≥ 1.5 の有理数 k について彩色多項式を評価する多項式時間の近似アルゴリズムは存在しない。 辺彩色については、Vizingの証明の結果から最大 Δ+1 色で彩色するアルゴリズムが得られている。しかし、2つの候補値から辺彩色数を決定する問題はNP完全である。近似アルゴリズムの場合、Vizingの辺彩色数を求めるアルゴリズムの近似度は4/3であり、任意の ε > 0 について(4/3 − ε )-近似アルゴリズムは存在しない（P=NPでない限り）。これらは近似アルゴリズムについての最も古い論文である（近似度という記法は明確には使っていない）。
※この「計算量」の解説は、「グラフ彩色」の解説の一部です。
「計算量」を含む「グラフ彩色」の記事については、「グラフ彩色」の概要を参照ください。
計算量
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2012/07/29 08:43 UTC 版)
n個の点から静的なkd木を構築する場合、中央値を求めるアルゴリズムで変わる。単純にO(n log n) のソートを使って中央値を各レベルについて計算するとすると、全体として O(n log 2 n) の時間がかかる。 より高速な線形中央値探索アルゴリズム（例えば Cormen et al）を使う場合、計算量は O(n log n) になる。 平衡kd木への新たな点の挿入には、O(log n) の時間がかかる。 平衡kd木からの点の削除には、O(log n) の時間がかかる。 平衡kd木である軸に平行な範囲にある点を求める場合、 O(n1-1/d +k) の時間がかかる。ここで、k は報告される点の個数、d は kd木の次元である。
※この「計算量」の解説は、「kd木」の解説の一部です。
「計算量」を含む「kd木」の記事については、「kd木」の概要を参照ください。
計算量
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/02/16 08:45 UTC 版)
双方向連結リストによる実装では、全ての操作の時間計算量はO(1)である。 動的配列の場合、追加操作の最悪時間計算量はO(n)である。全ての操作の償却時間計算量はO(1)である。
※この「計算量」の解説は、「両端キュー」の解説の一部です。
「計算量」を含む「両端キュー」の記事については、「両端キュー」の概要を参照ください。
計算量
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/08/22 13:42 UTC 版)
「ポラード・ロー素因数分解法」の記事における「計算量」の解説
このアルゴリズムでは、実行時間と素因数発見確率がトレードオフの関係にある。n が同じ桁数の2種類の素数の積であるとき、O(n1/4 polylog(n)) ステップ実行することで発見確率が約50%となる。なお、これはヒューリスティックによる概算であり、このアルゴリズムの正確な解析は未解決の問題である。
※この「計算量」の解説は、「ポラード・ロー素因数分解法」の解説の一部です。
「計算量」を含む「ポラード・ロー素因数分解法」の記事については、「ポラード・ロー素因数分解法」の概要を参照ください。
計算量
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/10/07 05:14 UTC 版)
要素数 n のスプレー木で m 回のアクセスのシーケンス S の最悪実行時間について、いくつかの定理と予想が存在する。 平衡定理 (balance theorem) シーケンス S を実行するコストは O ( m ( log n + 1 ) + n log n ) {\displaystyle O(m(\log n+1)+n\log n)\,\!} である。すなわち、スプレー木は少なくとも n 回のアクセスのシーケンスにおいて、静的平衡2分探索木と同程度の性能を発揮する。 静的最適性定理 (static optimality theorem) S において要素 i にアクセスする回数を q i {\displaystyle q_{i}} とする。すると S を実行するコストは O ( m + ∑ i = 1 n q i log m q i ) {\displaystyle O{\Bigl (}m+\sum _{i=1}^{n}q_{i}\log {\frac {m}{q_{i}}}{\Bigr )}} となる。すなわち、スプレー木は少なくとも n 回のアクセスのシーケンスにおいて、最適化された静的平衡2分探索木と同程度の性能を発揮する。 静的指定理 (static finger theorem) S において j t h {\displaystyle j^{th}} 番目にアクセスされる要素を i j {\displaystyle i_{j}} とし、f を任意の固定要素（これを指 finger と呼ぶ）とする。すると S を実行するコストは O ( m + n log n + ∑ j = 1 m log ( | i j − f | + 1 ) ) {\displaystyle O{\Bigl (}m+n\log n+\sum _{j=1}^{m}\log(|i_{j}-f|+1){\Bigr )}} となる。 ワーキングセット定理 (working set theorem) j 番目のアクセスと以前に同じ要素 i j {\displaystyle i_{j}} がアクセスされた間にアクセスされた別々の要素の個数を t ( j ) {\displaystyle t(j)} とする。するとS を実行するコストは O ( m + n log n + ∑ j = 1 m log ( t ( j ) + 1 ) ) {\displaystyle O{\Bigl (}m+n\log n+\sum _{j=1}^{m}\log(t(j)+1){\Bigr )}} となる。 動的指定理 (dynamic finger theorem) S を実行するコストは O ( m + n + ∑ j = 1 m log ( | i j + 1 − i j | + 1 ) ) {\displaystyle O{\Bigl (}m+n+\sum _{j=1}^{m}\log(|i_{j+1}-i_{j}|+1){\Bigr )}} である。 走査定理 (scanning theorem) 逐次アクセス定理とも呼ばれる。スプレー木の n 個の要素に対称的順序でアクセスすると、スプレー木の初期状態に関わらず Θ ( n ) {\displaystyle \Theta (n)\,\!} の時間がかかる。これまでに証明された最もきつい上限は 4.5 n {\displaystyle 4.5n} である。
※この「計算量」の解説は、「スプレー木」の解説の一部です。
「計算量」を含む「スプレー木」の記事については、「スプレー木」の概要を参照ください。
計算量
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/12/05 08:32 UTC 版)
V は頂点の数、E は辺の数。「重みが最小の辺」をどのように探索するかで計算量が変わる。 使用するデータ構造計算量単純な集合探索と隣接行列 O ( V 2 ) {\displaystyle O(V^{2})} 優先度付きキュー（二分ヒープ）と隣接リスト O ( ( V + E ) log V ) = O ( E log V ) {\displaystyle O((V+E)\log V)=O(E\log V)} 優先度付きキュー（フィボナッチヒープ）と隣接リスト O ( E + V log V ) {\displaystyle O(E+V\log V)} グラフを隣接行列で表した単純な実装で、重みの配列を探索して重みが最小の辺を求める場合、 O ( V 2 ) {\displaystyle O(V^{2})} の時間がかかる。単純な二分ヒープと隣接リストを使うと、 O ( ( V + E ) log V ) {\displaystyle O((V+E)\log V)} の時間がかかる。より洗練されたフィボナッチヒープを使うと、E が Ω ( V log V ) {\displaystyle \Omega (V\log V)} の程度まで稠密であれば、時間は O ( E + V log V ) {\displaystyle O(E+V\log V)} とかなり改善される。
※この「計算量」の解説は、「プリム法」の解説の一部です。
「計算量」を含む「プリム法」の記事については、「プリム法」の概要を参照ください。
計算量
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/01/03 14:40 UTC 版)
計算量（最大ヒープ）操作最悪計算量平均計算量最大値の取得O(1) O(1) 要素数の取得O(1) O(1) 追加O(log n) O(1) 削除O(log n) O(log n) 値の更新O(log n) O(1) 平均計算量だけでなく、最悪計算量も O(1) にしたい場合は、他のヒープ構造を検討するべきだが、二分ヒープを配列で実装した場合、計算量の定数項分が、一般的に他のアルゴリズムよりも小さく、現実的には二分ヒープが最速である場合も多く、libstdc++ (gcc) の priority_queue の実装ではプリミティブ型の場合は二分ヒープの使用を薦めている。フィボナッチヒープを使った場合、平均計算量ではなく償却計算量で、追加・更新が O(1)、削除が O(log n) になる。
※この「計算量」の解説は、「二分ヒープ」の解説の一部です。
「計算量」を含む「二分ヒープ」の記事については、「二分ヒープ」の概要を参照ください。
- 計算量のページへのリンク
