計算量とは? わかりやすく解説

計算量

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2018/12/11 07:56 UTC 版)

多角形の三角形分割」の記事における「計算量」の解説

長き渡って単純多角形を O ( n log ⁡ n ) {\displaystyle O(n\log n)} 時間より高速三角形分割アルゴリズム未発であったその後Tarjan & Van Wyk (1988)は O ( n loglog ⁡ 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時間 4138年 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」の記事における「計算量」の解説

DBSCANデータベース各点訪れる。複数訪れることもある(たとえば、異なクラスタへの候補として)。しかし、実践考慮のため、時間計算量はたいてい regionQuery の呼び出し回数によって支配されるDBSCAN各点そのようなクエリをまさに 1 度だけ実行し、O(log n) で近隣クエリ(en:Fixed-radius_near_neighbors)を実行するインデックス構造使用されるならば、O(n log n) の全体平均ランタイム複雑性獲得される(パラメータ ε が意味のある中で選ばれたならば。すなわち、平均して O(log n) の点が返される場合ならば)。加速させるようなインデックス構造使用しない場合、または縮退データ(たとえばすべての点が ε より小さい距離内にある)の場合は、その最悪計算時間は O() のままであるサイズ (-n)/2 の距離行列は距離の再計算回避するために出現しうるが、これは O() のメモリを必要とする。一方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 版)

kd木」の記事における「計算量」の解説

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 + 1i 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) になる。

※この「計算量」の解説は、「二分ヒープ」の解説の一部です。
「計算量」を含む「二分ヒープ」の記事については、「二分ヒープ」の概要を参照ください。

ウィキペディア小見出し辞書の「計算量」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「計算量」の関連用語

計算量のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



計算量のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaの多角形の三角形分割 (改訂履歴)、クラメルの公式 (改訂履歴)、ポラード・ロー離散対数アルゴリズム (改訂履歴)、ダイクストラ法 (改訂履歴)、ユークリッドの互除法 (改訂履歴)、ブルーフカ法 (改訂履歴)、最長共通部分列問題 (改訂履歴)、クワイン・マクラスキー法 (改訂履歴)、DBSCAN (改訂履歴)、フィボナッチヒープ (改訂履歴)、ソート (改訂履歴)、グラフ彩色 (改訂履歴)、kd木 (改訂履歴)、両端キュー (改訂履歴)、ポラード・ロー素因数分解法 (改訂履歴)、スプレー木 (改訂履歴)、プリム法 (改訂履歴)、二分ヒープ (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS