数学演算の計算複雑性

{\displaystyle N} — アルゴリズム解析で一般的に使用される関数のグラフで、演算回数を示す。 $N$ 入力サイズとの比較 $n$ 各関数について

以下の表は、一般的な数学演算のためのさまざまなアルゴリズムの計算複雑度を示しています。

ここで、複雑性とは、マルチテープチューリングマシン上で計算を実行する際の時間複雑性を指します。^[¹^]使用されている表記法の説明については、ビッグオー記法を参照してください。

注: 乗算アルゴリズムの種類が多岐にわたるため、 $M(n)$ 以下は、選択された乗算アルゴリズムの複雑さを表します。

算術関数

この表は、整数に対する数学演算の複雑さを示しています。

より強力な計算モデル、特にポインタマシン、そしてそれに伴う単位コストランダムアクセスマシンでは、2 つの $nビット数を$ O ( n )の時間で乗算することが可能です。^{[ 6 ]}

代数関数

ここでは多項式に対する演算を考え、 $n は$ その次数を表します。係数については単位コストモデルを使用し、数値のビット数を無視します。実際には、これは係数が機械整数であると仮定することを意味します。このセクションでは $M(n)$ 次数が最大での 2 つの多項式を乗算するのに必要な時間を示します $n$ [ ⁷^]^：²⁴²

特殊機能

このセクションで紹介されている方法の多くは、Borwein & Borwein ^{[ 8 ]に記載されています。}

基本関数

基本関数は、算術演算、指数関数（ $\exp$ )、自然対数( $\log$ )、三角関数( $\sin ,\cos$ ）とその逆関数。すべての基本関数は解析的であり、ニュートン法によって逆関数を求めることができるため、基本関数の複雑さはその逆関数の複雑さと等価である。特に、 $\exp$ または $\log$ 複素領域において、ある複雑さで計算できる関数があれば、その複雑さは他のすべての基本関数に対しても達成可能である。

以下にサイズを示します $n$ これは、関数を評価する際の精度桁数を指します。

不明 $O(M(n)\log n)$ は、初等関数の最適な複雑度です。最もよく知られている下限は、自明な下限です。 $\Omega$ $(M(n))$ 。

非初等関数

数学定数

この表は、与えられた定数の近似値を計算する複雑さを示しています。 $n$ 正しい数字。

数論

数論的計算のためのアルゴリズムは、計算数論において研究される。

行列代数

以下の複雑度数値は、固定精度浮動小数点演算や有限体上の演算の場合と同様に、個々の要素の算術演算の複雑度がO (1)であると仮定しています。

2005年に、ヘンリー・コーン、ロバート・クラインバーグ、バラージュ・セゲディ、クリス・ウマンスは、2つの異なる予想のいずれかが、行列乗算の指数が2であることを意味することを示した。^{[ 38 ]}

変換する

関数の変換（特に積分変換）を計算するためのアルゴリズムは、数学のあらゆる分野、特に解析学や信号処理において広く用いられている。

注記

↑この準指数関数的時間の形式は、すべてに有効です $\varepsilon >0$ 複雑性のより正確な形式は次のように表すことができます。 $O{\mathord {\left(\exp {\sqrt[{3}]{{\frac {64}{9}}b(\log b)^{2}}}\right)}}.$

参考文献

1 2シェーンハーゲ、A.グローテフェルト、AFW。ヴェッター、E. (1994)。高速アルゴリズム - マルチテープチューリングマシンの実装。 BI Wissenschafts-Verlag。ISBN 978-3-411-16891-0OCLC 897602049
↑クヌート 1997
↑ Harvey, D.; Van Der Hoeven, J. (2021). "Integer multiplication in time O (n log n)" (PDF) . Annals of Mathematics . 193 (2): 563– 617. doi : 10.4007/annals.2021.193.2.4 . S2CID 109934776 .
↑ Klarreich, Erica (2019年12月)「乗算は速度制限に達する」Commun. ACM 63 ( 1): 11– 13. doi : 10.1145/3371387 . S2CID 209450552 .
↑ブルニケル、クリストフ;ツィーグラー、ヨアヒム (1998)。高速再帰除算。マックス・プランク情報研究所の活動。ザールブリュッケン: MPI Informatik Bibliothek & Dokumentation。OCLC 246319574。 MPII-98-1-022。
↑アーノルドのシェーンハーゲ (1980)。「ストレージ変更マシン」。SIAM ジャーナルオンコンピューティング。9 (3): 490–508。土井: 10.1137/0209036。
1 2 3 4 von zur Gathen、J.ゲルハルト、J. (2013)。現代コンピュータ代数(第 3版)。ケンブリッジ大学出版局。ISBN 9781139856065。
↑ Borwein, J.; Borwein, P. (1987). Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity . Wiley. ISBN 978-0-471-83138-9. OCLC 755165897 .
↑チャドノフスキー、デイヴィッド；チャドノフスキー、グレゴリー（1988）。「ラマヌジャンによる近似と複素乗算」。ラマヌジャン再考：百年祭会議議事録。アカデミック・プレス。375–472頁。ISBN 978-0-01-205856-5。
↑ Brent, Richard P. (2014) [1975]. "多重精度零点検出法と基本関数評価の複雑性" . Traub, JF (編). Analytic Computational Complexity . Elsevier. pp. 151–176 . arXiv : 1004.3412 . ISBN 978-1-4832-5789-1。
1 2 Richard P. Brent (2020), The Borwein Brothers, Pi and the AGM , Springer Proceedings in Mathematics & Statistics, vol. 313, arXiv : 1802.07558 , doi : 10.1007/978-3-030-36568-4 , ISBN 978-3-030-36567-7S2CID 214742997
↑ Sorenson, J. (1994). "2 つの高速 GCD アルゴリズム". Journal of Algorithms . 16 (1): 110– 144. doi : 10.1006/jagm.1994.1006 .
↑ Crandall, R.; Pomerance, C. (2005). "アルゴリズム 9.4.7 (Stehlé-Zimmerman バイナリ再帰的最大公約数)" .素数 ― 計算論的視点(第 2版). Springer. pp. 471–3 . ISBN 978-0-387-28979-3。
↑ Möller N (2008). "On Schönhage's algorithm and subquadratic integer gcd computation" (PDF) . Mathematics of Computation . 77 (261): 589– 607. Bibcode : 2008MaCom..77..589M . doi : 10.1090/S0025-5718-07-02017-0 .
↑ Bernstein, DJ 「最悪ケースの整数を法とする非平方数を見つけるためのより高速なアルゴリズム」。
↑ブレント、リチャード P.、ツィンマーマン、ポール (2010)。「 $O(M(n)\log n)$ 「ヤコビ記号のアルゴリズム」。国際アルゴリズム数論シンポジウム。Springer。pp. 83–95。arXiv : 1004.2091。doi : 10.1007 /978-3-642-14518-6_10。ISBN 978-3-642-14518-6. S2CID 7632655 .
↑ Borwein, P. (1985). "階乗計算の複雑さについて". Journal of Algorithms . 6 (3): 376–380 . doi : 10.1016/0196-6774(85)90006-9 .
↑ Lenstra jr., HW ; Pomerance, Carl (2019). "ガウス周期による素数判定" (PDF) . Journal of the European Mathematical Society . 21 (4): 1229– 69. doi : 10.4171/JEMS/861 . hdl : 21.11116/0000-0005-717D-0 .
↑ Tao, Terence (2010). "1.11 AKS素数判定法" . An epsilon of room, II: Pages from year three of a mathematical blog . Graduate Studies in Mathematics. Vol. 117. American Mathematical Society. pp. 82–86 . doi : 10.1090/gsm/117 . ISBN 978-0-8218-5280-4MR 2780010 .
↑ Morain, F. (2007). "楕円曲線素数判定アルゴリズムの漸近的に高速なバージョンの実装". Mathematics of Computation . 76 (257): 493–505 . arXiv : math/0502097 . Bibcode : 2007MaCom..76..493M . doi : 10.1090 / S0025-5718-06-01890-4 . MR 2261033. S2CID 133193 .
↑ Pomerance, Carl ; Selfridge, John L. ; Wagstaff, Jr., Samuel S. (1980 年 7 月). "The pseudoprimes to 25·10 ⁹ " (PDF) . Mathematics of Computation . 35 (151): 1003– 26. doi : 10.1090/S0025-5718-1980-0572872-7 . JSTOR 2006210 .
↑ Baillie, Robert; Wagstaff, Jr., Samuel S. (1980 年 10 月). "Lucas Pseudoprimes" (PDF) . Mathematics of Computation . 35 (152): 1391– 1417. doi : 10.1090/S0025-5718-1980-0583518-6 . JSTOR 2006406 . MR 0583518 .
1 2 Monier, Louis (1980). "2 つの効率的な確率的素数判定アルゴリズムの評価と比較" . Theoretical Computer Science . 12 (1): 97– 108. doi : 10.1016/0304-3975(80)90007-9 . MR 0582244 .
↑ Alman, Josh; Williams, Virginia Vassilevska (2020)、「改良されたレーザー法と高速な行列乗算」、第32回ACM-SIAM離散アルゴリズムシンポジウム（SODA 2021）、pp. 522–539、arXiv : 2010.05846、doi : 10.1137/1.9781611976465.32、ISBN 978-1-61197-646-5S2CID 222290442
↑ Davie, AM; Stothers, AJ (2013)、「行列乗算の複雑さに関する改善された上限」、Proceedings of the Royal Society of Edinburgh、143A (2): 351–370、doi : 10.1017/S0308210511001648、S2CID 113401430
↑ Vassilevska Williams, Virginia (2014), 「Coppersmith-Winograd の障壁を破る: O(n ^2.373 ) 時間で行列を乗算する」
↑ Le Gall, François (2014), "Powers of tensors and fast matrix multiplication", Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation — ISSAC '14 , p. 23, arXiv : 1401.7714 , Bibcode : 2014arXiv1401.7714L , doi : 10.1145/2608628.2627493 , ISBN 9781450325011S2CID 353236
1 2 Le Gall, François; Urrutia, Floren (2018). 「Coppersmith-Winogradテンソルのべき乗を用いた改良された矩形行列乗算」。Czumaj, Artur (編)『第29回ACM-SIAM離散アルゴリズムシンポジウム議事録』。産業応用数学会。doi : 10.1137 / 1.9781611975031.67。ISBN 978-1-61197-503-1. S2CID 33396059 .
↑ Pan, V. (1984). "行列乗算を高速化するにはどうすればよいか？". SIAM Review . 26 (3): 393–415 . doi : 10.1137/1026076 .
↑ Knight, Philip A. (1995 年 5 月). "高速な矩形行列乗算と QR 分解" . Linear Algebra and Its Applications . 221 : 69– 81. doi : 10.1016/0024-3795(93)00230-w . ISSN 0024-3795 .
↑ Rote, G. (2001). "行列式とパフィアンに対する除算不要アルゴリズム：代数的アプローチと組み合わせ的アプローチ" (PDF) .計算離散数学. Springer. pp. 119–135 . ISBN 3-540-45506-X。
↑ Kaltofen, Erich; Villard, Gilles (2005). "On the complexity of computing determinants" . Computational Complexity . 13 ( 3–4 ): 91–130 . doi : 10.1007/s00037-004-0185-3 .
↑ Bunch, James R.; Hopcroft, John E. (1974). "高速行列乗算による三角行列の因数分解と逆行列の計算". Mathematics of Computation . 28 (125): 231–236 . doi : 10.1090/S0025-5718-1974-0331751-8 .
↑ＪＢ州フレーリー；ボーリガード、RA (1987)。線形代数(第 3版)。アディソン・ウェスリー。 p. 95.ISBN 978-0-201-15459-7。
↑ Preparata, FP; Sarwate, DV (1978年4月) 「高速行列反転における改良された並列プロセッサ」 Information Processing Letters . 7 (3): 148– 150. doi : 10.1016/0020-0190(78)90079-0 .
↑ Galil, Zvi; Pan, Victor (1989年1月16日). "行列の行列式と逆行列の並列評価" . Information Processing Letters . 30 (1): 148– 150. doi : 10.1016/0020-0190(89)90173-7 .その中で、 $O(n^{3})$ 期間が短縮される
↑ Neiger, Vincent; Pernet, Clément (2021年12月) 「行列乗算の時間における特性多項式の決定論的計算」 Journal of Complexity.67.arXiv : 2010.04662.doi : 10.1016 / j.jco.2021.101572 .
↑ Cohn, Henry; Kleinberg, Robert; Szegedy, Balazs; Umans, Chris (2005). "行列乗算のための群論的アルゴリズム".第46回コンピュータサイエンス基礎に関する年次シンポジウム議事録. IEEE. pp. 379–388 . arXiv : math.GR/0511460 . doi : 10.1109/SFCS.2005.39 . ISBN 0-7695-2468-0. S2CID 6429088 .

さらに読む

ブレント、リチャード・P.、ツィンマーマン、ポール（2010）。現代コンピュータ算術。ケンブリッジ大学出版局。ISBN 978-0-521-19469-3。
クヌース、ドナルド・アーヴィン（1997）。半数値アルゴリズム。コンピュータプログラミングの技法。第 2巻（第3 版）。アディソン・ウェスリー。ISBN 978-0-201-89684-8。

[24] この準指数関数的時間の形式は、すべてに有効です $\varepsilon >0$ 複雑性のより正確な形式は次のように表すことができます。 $O{\mathord {\left(\exp {\sqrt[{3}]{{\frac {64}{9}}b(\log b)^{2}}}\right)}}.$

[Schonhage-1] 1 2シェーンハーゲ、A.グローテフェルト、AFW。ヴェッター、E. (1994)。高速アルゴリズム - マルチテープチューリングマシンの実装。 BI Wissenschafts-Verlag。ISBN 978-3-411-16891-0OCLC 897602049

[2] クヌート 1997

[3] Harvey, D.; Van Der Hoeven, J. (2021). "Integer multiplication in time O (n log n)" (PDF) . Annals of Mathematics . 193 (2): 563– 617. doi : 10.4007/annals.2021.193.2.4 . S2CID 109934776 .

[4] Klarreich, Erica (2019年12月)「乗算は速度制限に達する」Commun. ACM 63 ( 1): 11– 13. doi : 10.1145/3371387 . S2CID 209450552 .

[5] ブルニケル、クリストフ;ツィーグラー、ヨアヒム (1998)。高速再帰除算。マックス・プランク情報研究所の活動。ザールブリュッケン: MPI Informatik Bibliothek & Dokumentation。OCLC 246319574。 MPII-98-1-022。

[6] アーノルドのシェーンハーゲ (1980)。「ストレージ変更マシン」。SIAM ジャーナルオンコンピューティング。9 (3): 490–508。土井: 10.1137/0209036。

[vzG-7] 1 2 3 4 von zur Gathen、J.ゲルハルト、J. (2013)。現代コンピュータ代数(第 3版)。ケンブリッジ大学出版局。ISBN 9781139856065。

[8] Borwein, J.; Borwein, P. (1987). Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity . Wiley. ISBN 978-0-471-83138-9. OCLC 755165897 .

[9] チャドノフスキー、デイヴィッド；チャドノフスキー、グレゴリー（1988）。「ラマヌジャンによる近似と複素乗算」。ラマヌジャン再考：百年祭会議議事録。アカデミック・プレス。375–472頁。ISBN 978-0-01-205856-5。

[10] Brent, Richard P. (2014) [1975]. "多重精度零点検出法と基本関数評価の複雑性" . Traub, JF (編). Analytic Computational Complexity . Elsevier. pp. 151–176 . arXiv : 1004.3412 . ISBN 978-1-4832-5789-1。

[brent-11] 1 2 Richard P. Brent (2020), The Borwein Brothers, Pi and the AGM , Springer Proceedings in Mathematics & Statistics, vol. 313, arXiv : 1802.07558 , doi : 10.1007/978-3-030-36568-4 , ISBN 978-3-030-36567-7S2CID 214742997

[12] Sorenson, J. (1994). "2 つの高速 GCD アルゴリズム". Journal of Algorithms . 16 (1): 110– 144. doi : 10.1006/jagm.1994.1006 .

[13] Crandall, R.; Pomerance, C. (2005). "アルゴリズム 9.4.7 (Stehlé-Zimmerman バイナリ再帰的最大公約数)" .素数 ― 計算論的視点(第 2版). Springer. pp. 471–3 . ISBN 978-0-387-28979-3。

[14] Möller N (2008). "On Schönhage's algorithm and subquadratic integer gcd computation" (PDF) . Mathematics of Computation . 77 (261): 589– 607. Bibcode : 2008MaCom..77..589M . doi : 10.1090/S0025-5718-07-02017-0 .

[15] Bernstein, DJ 「最悪ケースの整数を法とする非平方数を見つけるためのより高速なアルゴリズム」。

[16] ブレント、リチャード P.、ツィンマーマン、ポール (2010)。「 $O(M(n)\log n)$ 「ヤコビ記号のアルゴリズム」。国際アルゴリズム数論シンポジウム。Springer。pp. 83–95。arXiv : 1004.2091。doi : 10.1007 /978-3-642-14518-6_10。ISBN 978-3-642-14518-6. S2CID 7632655 .

[17] Borwein, P. (1985). "階乗計算の複雑さについて". Journal of Algorithms . 6 (3): 376–380 . doi : 10.1016/0196-6774(85)90006-9 .

[Lenstra19-18] Lenstra jr., HW ; Pomerance, Carl (2019). "ガウス周期による素数判定" (PDF) . Journal of the European Mathematical Society . 21 (4): 1229– 69. doi : 10.4171/JEMS/861 . hdl : 21.11116/0000-0005-717D-0 .

[tao-aks-19] Tao, Terence (2010). "1.11 AKS素数判定法" . An epsilon of room, II: Pages from year three of a mathematical blog . Graduate Studies in Mathematics. Vol. 117. American Mathematical Society. pp. 82–86 . doi : 10.1090/gsm/117 . ISBN 978-0-8218-5280-4MR 2780010 .

[morain-20] Morain, F. (2007). "楕円曲線素数判定アルゴリズムの漸近的に高速なバージョンの実装". Mathematics of Computation . 76 (257): 493–505 . arXiv : math/0502097 . Bibcode : 2007MaCom..76..493M . doi : 10.1090 / S0025-5718-06-01890-4 . MR 2261033. S2CID 133193 .

[PSW-21] Pomerance, Carl ; Selfridge, John L. ; Wagstaff, Jr., Samuel S. (1980 年 7 月). "The pseudoprimes to 25·10 ⁹ " (PDF) . Mathematics of Computation . 35 (151): 1003– 26. doi : 10.1090/S0025-5718-1980-0572872-7 . JSTOR 2006210 .

[lpsp-22] Baillie, Robert; Wagstaff, Jr., Samuel S. (1980 年 10 月). "Lucas Pseudoprimes" (PDF) . Mathematics of Computation . 35 (152): 1391– 1417. doi : 10.1090/S0025-5718-1980-0583518-6 . JSTOR 2006406 . MR 0583518 .

[monier-23] 1 2 Monier, Louis (1980). "2 つの効率的な確率的素数判定アルゴリズムの評価と比較" . Theoretical Computer Science . 12 (1): 97– 108. doi : 10.1016/0304-3975(80)90007-9 . MR 0582244 .

[aw20-25] Alman, Josh; Williams, Virginia Vassilevska (2020)、「改良されたレーザー法と高速な行列乗算」、第32回ACM-SIAM離散アルゴリズムシンポジウム（SODA 2021）、pp. 522–539、arXiv : 2010.05846、doi : 10.1137/1.9781611976465.32、ISBN 978-1-61197-646-5S2CID 222290442

[26] Davie, AM; Stothers, AJ (2013)、「行列乗算の複雑さに関する改善された上限」、Proceedings of the Royal Society of Edinburgh、143A (2): 351–370、doi : 10.1017/S0308210511001648、S2CID 113401430

[27] Vassilevska Williams, Virginia (2014), 「Coppersmith-Winograd の障壁を破る: O(n ^2.373 ) 時間で行列を乗算する」

[28] Le Gall, François (2014), "Powers of tensors and fast matrix multiplication", Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation — ISSAC '14 , p. 23, arXiv : 1401.7714 , Bibcode : 2014arXiv1401.7714L , doi : 10.1145/2608628.2627493 , ISBN 9781450325011S2CID 353236

[Le_Gall-29] 1 2 Le Gall, François; Urrutia, Floren (2018). 「Coppersmith-Winogradテンソルのべき乗を用いた改良された矩形行列乗算」。Czumaj, Artur (編)『第29回ACM-SIAM離散アルゴリズムシンポジウム議事録』。産業応用数学会。doi : 10.1137 / 1.9781611975031.67。ISBN 978-1-61197-503-1. S2CID 33396059 .

[30] Pan, V. (1984). "行列乗算を高速化するにはどうすればよいか？". SIAM Review . 26 (3): 393–415 . doi : 10.1137/1026076 .

[31] Knight, Philip A. (1995 年 5 月). "高速な矩形行列乗算と QR 分解" . Linear Algebra and Its Applications . 221 : 69– 81. doi : 10.1016/0024-3795(93)00230-w . ISSN 0024-3795 .

[32] Rote, G. (2001). "行列式とパフィアンに対する除算不要アルゴリズム：代数的アプローチと組み合わせ的アプローチ" (PDF) .計算離散数学. Springer. pp. 119–135 . ISBN 3-540-45506-X。

[33] Kaltofen, Erich; Villard, Gilles (2005). "On the complexity of computing determinants" . Computational Complexity . 13 ( 3–4 ): 91–130 . doi : 10.1007/s00037-004-0185-3 .

[34] Bunch, James R.; Hopcroft, John E. (1974). "高速行列乗算による三角行列の因数分解と逆行列の計算". Mathematics of Computation . 28 (125): 231–236 . doi : 10.1090/S0025-5718-1974-0331751-8 .

[35] ＪＢ州フレーリー；ボーリガード、RA (1987)。線形代数(第 3版)。アディソン・ウェスリー。 p. 95.ISBN 978-0-201-15459-7。

[36] Preparata, FP; Sarwate, DV (1978年4月) 「高速行列反転における改良された並列プロセッサ」 Information Processing Letters . 7 (3): 148– 150. doi : 10.1016/0020-0190(78)90079-0 .

[37] Galil, Zvi; Pan, Victor (1989年1月16日). "行列の行列式と逆行列の並列評価" . Information Processing Letters . 30 (1): 148– 150. doi : 10.1016/0020-0190(89)90173-7 .その中で、 $O(n^{3})$ 期間が短縮される

[38] Neiger, Vincent; Pernet, Clément (2021年12月) 「行列乗算の時間における特性多項式の決定論的計算」 Journal of Complexity.67.arXiv : 2010.04662.doi : 10.1016 / j.jco.2021.101572 .

[39] Cohn, Henry; Kleinberg, Robert; Szegedy, Balazs; Umans, Chris (2005). "行列乗算のための群論的アルゴリズム".第46回コンピュータサイエンス基礎に関する年次シンポジウム議事録. IEEE. pp. 379–388 . arXiv : math.GR/0511460 . doi : 10.1109/SFCS.2005.39 . ISBN 0-7695-2468-0. S2CID 6429088 .

[

[ 6 ]

7

[ 8 ]に記載されています。

[ 38 ]

算術関数

代数関数

特殊機能

基本関数

非初等関数

数学定数

数論

行列代数

変換する

注記

参考文献

さらに読む

関連するトピック

数学演算

アルゴリズム

計算複雑度

ここで、複雑性とは、マルチテープチューリングマシン