Výpočetní složitost matematických operací - Computational complexity of mathematical operations
![]() | tento článek potřebuje další citace pro ověření.Dubna 2015) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |

V následujících tabulkách je uveden seznam výpočetní složitost různých algoritmy pro běžné matematické operace.
Zde se složitost týká časová složitost provádění výpočtů na a multitape Turingův stroj.[1] Vidět velká O notace pro vysvětlení použité notace.
Poznámka: Vzhledem k rozmanitosti multiplikačních algoritmů níže znamená složitost zvoleného multiplikačního algoritmu.
Aritmetické funkce
Úkon | Vstup | Výstup | Algoritmus | Složitost |
---|---|---|---|---|
Přidání | Dva - číslice, a | Jeden -místné číslo | Doplnění učebnice s nošením | |
Odčítání | Dva - číslice, a | Jeden -místné číslo | Odčítání učebnice s výpůjčkou | |
Násobení | Dva -místná čísla | Jeden -místné číslo | Dlouhé násobení učebnice | |
Algoritmus Karatsuba | ||||
3cestný Násobení Toom – Cook | ||||
-way Toom – Cook násobení | ||||
Toom – Cook na smíšené úrovni (Knuth 4.3.3-T)[2] | ||||
Schönhage – Strassenův algoritmus | ||||
Fürerův algoritmus[3] | ||||
Harvey-Hoevenův algoritmus[4] [5] | ||||
Divize | Dva -místná čísla | Jeden -místné číslo | Dlouhé dělení učebnice | |
Burnikel-Ziegler Divide-and-Conquer Division [6] | ||||
Divize Newton – Raphson | ||||
Odmocnina | Jeden -místné číslo | Jeden -místné číslo | Newtonova metoda | |
Modulární umocňování | Dva -místná celá čísla a -bitový exponent | Jeden -místné celé číslo | Opakované množení a redukce | |
Umocňování čtvercem | ||||
Umocnění s Montgomeryho redukce |
Algebraické funkce
Úkon | Vstup | Výstup | Algoritmus | Složitost |
---|---|---|---|---|
Polynomiální hodnocení | Jeden polynom stupně s koeficienty pevné velikosti | Jedno číslo pevné velikosti | Přímé hodnocení | |
Hornerova metoda | ||||
Polynomiální gcd (přes nebo ) | Dva polynomy stupně s celočíselnými koeficienty pevné velikosti | Jeden polynom stupně | Euklidovský algoritmus | |
Rychlý euklidovský algoritmus (Lehmer)[7] |
Speciální funkce
Mnoho metod v této části je uvedeno v dokumentech Borwein a Borwein.[8]
Základní funkce
The základní funkce jsou konstruovány složením aritmetických operací, exponenciální funkce (), přirozený logaritmus (), trigonometrické funkce () a jejich inverze. Složitost elementární funkce je ekvivalentní složitosti její inverzní funkce, protože všechny elementární funkce jsou analytický a tedy invertibilní pomocí Newtonovy metody. Zejména pokud nebo v komplexní doméně lze vypočítat s určitou složitostí, pak je tato složitost dosažitelná pro všechny ostatní základní funkce.
Níže velikost odkazuje na počet číslic přesnosti, při kterých má být funkce vyhodnocena.
Algoritmus | Použitelnost | Složitost |
---|---|---|
Taylor série; opakovaná redukce argumentů (např. ) a přímý součet | ||
Taylorova řada; FFT -zrychlení na základě | ||
Taylorova řada; binární rozdělení + algoritmus bit-burst[9] | ||
Aritmeticko – geometrický průměr opakování[10] |
Není známo, zda je optimální složitost pro základní funkce. Nejznámější spodní mez je triviální mez .
Neelementární funkce
Funkce | Vstup | Algoritmus | Složitost |
---|---|---|---|
Funkce gama | -místné číslo | Série aproximace neúplná funkce gama | |
Opravené racionální číslo | Hypergeometrická řada | ||
, pro celé číslo. | Aritmeticko-geometrický průměr opakování | ||
Hypergeometrická funkce | -místné číslo | (Jak je popsáno v Borwein & Borwein) | |
Opravené racionální číslo | Hypergeometrická řada |
Matematické konstanty
Tato tabulka uvádí složitost výpočtu aproximací pro dané konstanty správné číslice.
Konstantní | Algoritmus | Složitost |
---|---|---|
Zlatý řez, | Newtonova metoda | |
Druhá odmocnina ze 2, | Newtonova metoda | |
Eulerovo číslo, | Binární rozdělení Taylorovy řady pro exponenciální funkci | |
Newtonova inverze přirozeného logaritmu | ||
Pi, | Binární rozdělení arktanové řady v Machinův vzorec | [11] |
Algoritmus Gauss – Legendre | [11] | |
Eulerova konstanta, | Sweeneyova metoda (aproximace z hlediska exponenciální integrál ) |
Teorie čísel
Algoritmy pro číslo teoretické výpočty jsou studovány v výpočetní teorie čísel.
Úkon | Vstup | Výstup | Algoritmus | Složitost |
---|---|---|---|---|
Největší společný dělitel | Dva -číselná celá čísla | Jedno celé číslo maximálně číslice | Euklidovský algoritmus | |
Binární algoritmus GCD | ||||
Levá, pravá k- binární binární algoritmus GCD[12] | ||||
Algoritmus Stehlé – Zimmermann[13] | ||||
Schönhage řízený euklidovský sestupový algoritmus[14] | ||||
Jacobi symbol | Dva -číselná celá čísla | , nebo | Schönhageem řízený euklidovský algoritmus sestupu[15] | |
Algoritmus Stehlé – Zimmermann[16] | ||||
Faktoriální | Kladné celé číslo menší než | Jeden -místné celé číslo | Násobení zdola nahoru | |
Binární rozdělení | ||||
Umocnění hlavních faktorů | ,[17] [1] | |||
Test primality | A -místné celé číslo | Pravda nebo lež | Test prvosti AKS | [18] [19] nebo [20][21], , za předpokladu Agrawalova domněnka |
Prokazatelnost eliptické křivky | heuristicky[22] | |||
Baityho-PSW test primality | [23][24] | |||
Miller – Rabinův test primality | [25] | |||
Test primality Solovay – Strassen | [25] | |||
Faktorizace celého čísla | A -bitové celé číslo | Soubor faktorů | Síto obecného čísla | [pozn. 1] |
Shorův algoritmus | , na kvantový počítač |
Maticová algebra
Následující čísla o složitosti předpokládají, že aritmetika s jednotlivými prvky má složitost Ó(1), jak je tomu u pevné přesnosti aritmetika s plovoucí desetinnou čárkou nebo operace na a konečné pole.
Úkon | Vstup | Výstup | Algoritmus | Složitost |
---|---|---|---|---|
Násobení matic | Dva matice | Jeden matice | Násobení matice učebnice | |
Strassenův algoritmus | ||||
Coppersmith – Winogradův algoritmus | ||||
Optimalizované algoritmy podobné CW[26][27][28] | ||||
Násobení matic | Jeden matice & jeden matice | Jeden matice | Násobení matice učebnice | |
Násobení matic | Jeden matice & jeden matice, pro některé | Jeden matice | Algoritmy uvedené v [29] | , kde jsou horní hranice jsou uvedeny v [29] |
Maticová inverze* | Jeden matice | Jeden matice | Eliminace Gauss-Jordan | |
Strassenův algoritmus | ||||
Coppersmith – Winogradův algoritmus | ||||
Optimalizované algoritmy podobné CW | ||||
Rozklad singulární hodnoty | Jeden matice | Jeden matice, jeden matice, & jeden matice | Bidiagonalizace a QR algoritmus | () |
Jeden matice, jeden matice, & jeden matice | Bidiagonalizace a QR algoritmus | () | ||
Rozhodující | Jeden matice | Jedno číslo | Laplaceova expanze | |
Algoritmus bez rozdělení[30] | ||||
LU rozklad | ||||
Bareissův algoritmus | ||||
Rychlé množení matic[31] | ||||
Zpět substituce | Trojúhelníková matice | řešení | Zpět substituce[32] |
V roce 2005 Henry Cohn, Robert Kleinberg, Balázs Szegedy, a Chris Umans ukázal, že jeden ze dvou různých domněnek by znamenal, že exponent násobení matice je 2.[33]
^* Kvůli možnosti blokové invertování matice, kde inverze an matice vyžaduje inverzi dvou polovičních matic a šesti násobení mezi dvěma polovičními maticemi, a protože maticové násobení má spodní hranici () operace,[34] lze ukázat, že a algoritmus rozděl a panuj , který používá blokovou inverzi k invertování maticových běhů se stejnou časovou složitostí jako algoritmus násobení matice, který se používá interně.[35]
Transformace
Algoritmy pro výpočet transformuje funkcí (zejména integrální transformace ) jsou široce používány ve všech oblastech matematiky, zejména analýza a zpracování signálu.
Úkon | Vstup | Výstup | Algoritmus | Složitost |
---|---|---|---|---|
Diskrétní Fourierova transformace | Konečná datová sekvence velikosti | Sada komplexních čísel | Rychlá Fourierova transformace |
Poznámky
- ^ Tato forma subexponenciálního času je platná pro všechny . Přesnější formu složitosti lze uvést jako
Reference
- ^ A b A. Schönhage, A.F.W. Grotefeld, E. Vetter: Rychlé algoritmy - implementace vícepásmového Turingova stroje, BI Wissenschafts-Verlag, Mannheim, 1994
- ^ D. Knuth. Umění počítačového programování, Svazek 2. Třetí vydání, Addison-Wesley 1997.
- ^ Martin Fürer. Rychlejší násobení celých čísel [https://web.archive.org/web/20130425232048/http://www.cse.psu.edu/~furer/Papers/mult.pdf archivováno 2013-04-25 na Wayback Machine. Sborník z 39. ročníku ACM Symposium on Theory of Computing, San Diego, Kalifornie, USA, 11. – 13. Června 2007, s. 55–67.
- ^ David Harvey, Joris van der Hoeven Násobení celého čísla v čase O (n log n). (2019).
- ^ Erica Klarreich. 2019. Násobení narazí na rychlostní limit. Commun. ACM 63, 1 (prosinec 2019), 11. – 13. doi:10.1145/3371387
- ^ Christoph Burnikel a Joachim Ziegler Rychlá rekurzivní divize Im Stadtwald, D- Saarbrucken 1998.
- ^ http://planetmath.org/fasteuclideanalgorithm
- ^ J. Borwein a P. Borwein. Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity. John Wiley 1987.
- ^ David a Gregory Chudnovsky. Aproximace a komplexní násobení podle Ramanujana. Ramanujan se vrátil„Academic Press, 1988, str. 375–472.
- ^ Richard P. Brent, Metody nulování s více přesností a složitost vyhodnocení elementárních funkcí, in: Analytic Computational Complexity (J. F. Traub, ed.), Academic Press, New York, 1975, 151–176.
- ^ A b Richard P. Brent (2020), Bratři Borweinovi, Pi a AGMSpringer Proceedings in Mathematics & Statistics, 313, arXiv:1802.07558, doi:10.1007/978-3-030-36568-4, ISBN 978-3-030-36567-7
- ^ J. Sorenson. (1994). "Dva rychlé GCD algoritmy". Journal of Algorithms. 16 (1): 110–144. doi:10.1006 / jagm.1994.1006.
- ^ R. Crandall a C. Pomerance. Prvočísla - výpočetní perspektiva. Druhé vydání, Springer 2005.
- ^ Möller N (2008). „Na Schönhageově algoritmu a subkvadratickém výpočtu celého čísla gcd“ (PDF). Matematika výpočtu. 77 (261): 589–607. Bibcode:2008MaCom..77..589M. doi:10.1090 / S0025-5718-07-02017-0.
- ^ Bernstein D J. „Rychlejší algoritmy pro nalezení nejhorších modulových nejhorších celých čísel“.
- ^ Richard P. Brent; Paul Zimmermann (2010). „An algoritmus pro symbol Jacobi ". arXiv:1004.2091 [cs.DS ].
- ^ Borwein, P. (1985). "O složitosti výpočtu faktoriálů". Journal of Algorithms. 6 (3): 376–380. doi:10.1016/0196-6774(85)90006-9.
- ^ H. W. Lenstra Jr. a Carl Pomerance, “Testování primality s Gaussovými obdobími ", předběžná verze 20. července 2005.
- ^ H. W. Lenstra ml. a Carl Pomerance, “Testování primality s Gaussovými obdobími Archivováno 2012-02-25 na Wayback Machine “, verze ze dne 12. dubna 2011.
- ^ Tao, Terence (2010). „1.11 Test prvočíselnosti AKS“. Epsilon místnosti, II: Stránky ze třetího roku matematického blogu. Postgraduální studium matematiky. 117. Providence, RI: American Mathematical Society. str. 82–86. doi:10,1090 / gsm / 117. ISBN 978-0-8218-5280-4. PAN 2780010.
- ^ Lenstra, Jr., H.W.; Pomerance, Carle (11. prosince 2016). „Testování primality s Gaussovými obdobími“ (PDF). Citovat deník vyžaduje
| deník =
(Pomoc) - ^ Morain, F. (2007). "Implementace asymptoticky rychlé verze algoritmu prokazujícího primitivitu eliptické křivky". Matematika výpočtu. 76 (257): 493–505. arXiv:matematika / 0502097. Bibcode:2007MaCom..76..493M. doi:10.1090 / S0025-5718-06-01890-4. PAN 2261033. S2CID 133193.
- ^ Carl Pomerance; John L. Selfridge; Samuel S. Wagstaff, Jr. (Červenec 1980). „Pseudoprimes na 25.109" (PDF). Matematika výpočtu. 35 (151): 1003–1026. doi:10.1090 / S0025-5718-1980-0572872-7. JSTOR 2006210.
- ^ Robert Baillie; Samuel S. Wagstaff, Jr. (Říjen 1980). „Lucas Pseudoprimes“ (PDF). Matematika výpočtu. 35 (152): 1391–1417. doi:10.1090 / S0025-5718-1980-0583518-6. JSTOR 2006406. PAN 0583518.
- ^ A b Monier, Louis (1980). "Vyhodnocení a srovnání dvou efektivních pravděpodobnostních algoritmů testování primality". Teoretická informatika. 12 (1): 97–108. doi:10.1016/0304-3975(80)90007-9. PAN 0582244.
- ^ Davie, A.M .; Stothers, A.J. (2013), „Vylepšená hranice pro složitost násobení matic“, Sborník Královské společnosti z Edinburghu, 143A (2): 351–370, doi:10.1017 / S0308210511001648
- ^ Vassilevska Williams, Virginie (2011), Prolomení bariéry Coppersmith-Winograd (PDF)
- ^ Le Gall, François (2014), „Powers of tensors and fast matrix multiplication“, Sborník 39. mezinárodního sympozia o symbolických a algebraických výpočtech (ISSAC 2014), arXiv:1401.7714, Bibcode:2014arXiv1401.7714L
- ^ A b Le Gall, François; Urrutia, Floren (2018). "Vylepšené obdélníkové násobení matic pomocí pravomocí tenzoru Coppersmith-Winograd". V Czumaj, Artur (ed.). Sborník z dvacátého devátého výročního sympozia ACM-SIAM o diskrétních algoritmech. Společnost pro průmyslovou a aplikovanou matematiku (SIAM). doi:10.1137/1.9781611975031.67. ISBN 978-1-61197-503-1. S2CID 33396059.
- ^ http://page.mi.fu-berlin.de/rote/Papers/pdf/Division-free+algorithms.pdf
- ^ Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974), Návrh a analýza počítačových algoritmů, Addison-Wesley, Theorem 6.6, s. 241
- ^ J. B. Fraleigh a R. A. Beauregard, „Linear Algebra,“ Addison-Wesley Publishing Company, 1987, str. 95.
- ^ Henry Cohn, Robert Kleinberg, Balazs Szegedy a Chris Umans. Skupinové teoretické algoritmy pro násobení matic. arXiv:matematika.GR/0511460. Sborník 46. výročního sympozia o základech informatiky„23. – 25. Října 2005, Pittsburgh, PA, IEEE Computer Society, s. 379–388.
- ^ Ran Raz. O složitosti maticového produktu. Ve sborníku z třicátého čtvrtého ročníku ACM symposia o teorii práce s počítačem. ACM Press, 2002. doi:10.1145/509907.509932.
- ^ T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Úvod do algoritmů, 3. vydání, MIT Press, Cambridge, MA, 2009, § 28.2.
Další čtení
- Brent, Richard P.; Zimmermann, Paul (2010). Moderní počítačová aritmetika. Cambridge University Press. ISBN 978-0-521-19469-3.
- Knuth, Donald Ervin (1997). Umění počítačového programování. Svazek 2: Seminumerické algoritmy (3. vyd.). Addison-Wesley. ISBN 978-0-201-89684-8.