Výpočetní složitost matematických operací
Následující tabulky uvádějí časovou složitost matematických operací. S ohledem na to, že efektivita značné části složitějších operací závisí na efektivitě implementace násobení, kterou používají, je v patřičných vzorcích použito pro naznačení této skutečnosti.
Aritmetické operace
| Operace | Vstup | Výstup | Algoritmus | Složitost |
|---|---|---|---|---|
| sčítání | dvě čísla o n číslicích | číslo o až n+1 číslicích | školské sčítání s přenosem | Θ(n) |
| odčítání | dvě čísla o n číslicích | číslo o až n+1 číslicích | školské odčítání s výpůjčkou | Θ(n) |
| násobení | dvě čísla o n číslicích | číslo o 2n číslicích | školské násobení | O(n2) |
| Karacubův algoritmus | O(n1,585) | |||
| trojcestné Toomovo–Cookovo násobení | O(n1,465) | |||
| k-cestné Toomovo–Cookovo násobení | O(nlog (2k − 1)/log k) | |||
| Toomovo-Cookovo násobení smíšené úrovně[1] | O() | |||
| Schönhageův–Strassenův algoritmus | O(n log n log log n) | |||
| Fürerův algoritmus[2] | O(n log n 2log* n) | |||
| dělení | dvě čísla o n číslicích | číslo o n číslicích | školské dělení | O(n2) |
| Newtonovo–Raphsonovo dělení | O(M(n)) | |||
| druhá odmocnina | číslo o n číslicích | číslo o až n číslicích | Newtonova metoda | O(M(n)) |
| modulární mocnění | dvě čísla až o n číslicích a jeden exponent o k číslicích | číslo o až n číslicích | opakované násobení a modulení | O(2kM(n)) |
| dvojkové mocnění | O(k M(n)) | |||
| mocnění s Montgomeryho redukcí | O(k M(n)) |
Algebraické funkce
| Operace | Vstup | Výstup | Algoritmus | Složitost |
|---|---|---|---|---|
| Vyhodnocení polynomu | Jeden polynom stupně n s pevně danou velikostí koeficientů | Jedno číslo omezené velikosti | Přímé vyhodnocení | Θ(n) |
| Hornerovo schéma | Θ(n) | |||
| Největší společný dělitel (nad okruhy Z[x] nebo T[x]) | Dva polynomy stupně n s koeficienty pevně dané velikosti | Jeden polynom stupně nejvýše n | Eukleidův algoritmus | O(n2) |
| Rychlý Eukleidův algoritmus [3] | O(n (log n)2 log log n) |
Speciální funkce
Elementární funkce
Elementární funkce je možné zkonstruovat skládáním aritmetických operací, jedná se o exponenciální funkci (exp), přirozený logaritmus (log) a o goniometrické funkce a funkce k nim (částečně) inverzní. Složitost elementárních funkcí je rovna složitosti funkcí k nim inverzních, protože všechny elementární funkce jsou analytické a tedy invertovatelné newtonovou metodou. Zejména platí, že je-li exponenciální funkce nebo logaritimická funkce vyčíslitelná s nějakou složitostí, jsou se stejnou složitostí vyčíslitelné i ostatní elementární funkce.
V tabulce níže se proměnnou n označuje požadovaný počet číslic přesnosti.
| Algoritmus | Použitelnost | Složitost |
|---|---|---|
| Taylorova řada; přímý součet a opakovaná redukce argumentu (t.j. exp(2x) = [exp(x)]2) | exp, log, sin, cos | O(n1/2 M(n)) |
| Taylorova řada; zrychlení pomocí rychlé Fourierovy transformace | exp, log, sin, cos | O(n1/3 (log n)2 M(n)) |
| Taylorova řada; binární dělení [4] | exp, log, sin, cos | O((log n)2 M(n)) |
| iterace aritmeticko-geometrického průměru | log | O(log n M(n)) |
Není známo, zda O(log n M(n)) představuje optimální složitost výpočtu elementárních funkcí. Největší známý dolní odhad je Ω(M(n)).
Neelementární funkce
| Funkce | Vstup | Algoritmus | Složitost |
|---|---|---|---|
| funkce Gama | číslo o n číslicích | Postupná aproximace neúplné funkce Gama | O(n1/2 (log n)2 M(n)) |
| pevně dané racionální číslo | hypergeometrické řady | O((log n)2 M(n)) | |
| m/24, m je celé číslo | iterace aritmeticko-geometrického průměru | O(log n M(n)) | |
| hypergeometrická funkce pFq | číslo o n číslicích | O(n1/2 (log n)2 M(n)) | |
| Pevně dané racionální číslo | Hypergeometrické řady | O((log n)2 M(n)) |
Matematické konstanty
Tabulka níže shrnuje výpočetní složitost úlohy získat hodnotu dané konstanty s přesností n číslic.
| Konstanta | Algoritmus | Složitost |
|---|---|---|
| Zlatý řez, φ | Metoda tečen | O(M(n)) |
| druhá odmocnina ze dvou, | Metoda tečen | O(M(n)) |
| Eulerovo číslo, e | Binární dělení Taylorových řad pro exponenciální funkci | O(log n M(n)) |
| Newtonův inverz přirozeného logaritmu | O(log n M(n)) | |
| Ludolfovo číslo, π | Binární dělení arctanové řady v Machinově vzorci | O((log n)2 M(n)) |
| Salaminův–Brentův algoritmus | O(log n M(n)) | |
| Eulerova–Mascheroniho konstanta, γ | Sweeneyho metoda | O((log n)2 M(n)) |
Teorie čísel
Složitosti výpočtů z teorie čísel se věnuje výpočtová teorie čísel.
| Operace | Vstup | Výstup | Algoritmus | Složitost |
|---|---|---|---|---|
| Největší společný dělitel | Dvě čísla o n číslicích | Číslo o nejvýše n číslicích | Eukleidův algoritmus | O(n2) |
| Steinův algoritmus | O(n2) | |||
| Levý/pravýk-ární Steinův algoritmus[5] | O(n2/ log n) | |||
| Stehlého–Zimmermannův algoritmus[6] | O(log n M(n)) | |||
| Schönhageho kontrolovaný eukleidovský sestup[7] | O(log n M(n)) | |||
| Jacobiho symbol | Dvě čísla o n číslicích | 0, −1, or 1 | ||
| Schönhageho kontrolovaný eukleidovský sestup[8] | O(log n M(n)) | |||
| Stehlého–Zimmermannův algoritmus[9] | O(log n M(n)) | |||
| Faktoriál | Pevně dané číslo m | Číslo o O(m log m) číslicích | Násobení odspodu | O(m2 log m) |
| Binární dělení | O(log m M(m log m)) | |||
| Umocňování prvočíselných dělitelů m | O(log log m M(m log m)),[10] O(M(m log m)) |
Maticová algebra
Hodnoty v následující tabulce jsou za platné za předpokládu, že maticové prvky lze násobit v konstantním čase.
| Operace | Vstup | Výstup | Algoritmus | Složitost |
|---|---|---|---|---|
| Násobení matic | Dvě matice rozměrů n×n | Jedna matice o rozměru n×n | Školské násobení | O(n3) |
| Strassenův algoritmus | O(n2,807) | |||
| Coppersmithův–Winogradův algoritmus | O(n2,376) | |||
| Williamsův algoritmus[11] | O(n2.373) | |||
| Násobení matic | jedna matice o rozměrech n×m a jedna matice o rozměrech m×p | jedna matice o rozměru n×p | Školské násobení | O(nmp) |
| Inverze matice | matice o rozměrech n×n | matice o rozměrech n×n | Gaussova–Jordanova eliminace | O(n3) |
| Strassenův algoritmus | O(n2,807) | |||
| Coppersmithův–Winogradův algoritmus | O(n2,376) | |||
| Williamsův algoritmus | O(n2,373) | |||
| Determinant | jedna matice o rozměrech n×n | jedna hodnota | Laplaceův rozvoj | O(n!) |
| LU dekompozice | O(n3) | |||
| Bareissův algoritmus | O(n3) | |||
| Rychlé násobení matic | O(n2,373) | |||
| Zpětné dosazení | trojúhelníková matice | n řešení | Zpětné dosazení | O(n2)[12] |
Reference
V tomto článku byl použit překlad textu z článku Computational complexity of mathematical operations na anglické Wikipedii.
- ↑ D. Knuth. The Art of Computer Programming, Volume 2. Third Edition, Addison-Wesley 1997.
- ↑ Martin Fürer. Faster Integer Multiplication Archivováno 25. 4. 2013 na Wayback Machine. Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11–13, 2007, pp. 55–67.
- ↑ http://planetmath.org/fasteuclideanalgorithm
- ↑ David and Gregory Chudnovsky. Approximations and complex multiplication according to Ramanujan. Ramanujan revisited, Academic Press, 1988, pp 375–472.
- ↑ J. Sorenson. Two Fast GCD Algorithms. Journal of Algorithms. 1994, s. 110–144. DOI 10.1006/jagm.1994.1006. (anglicky)
- ↑ R. Crandall & C. Pomerance. Prime Numbers – A Computational Perspective. Second Edition, Springer 2005.
- ↑ Möller N. On Schönhage's algorithm and subquadratic integer gcd computation. Mathematics of Computation. 2008, s. 589–607. Dostupné online. DOI 10.1090/S0025-5718-07-02017-0. (anglicky)
- ↑ Bernstein D J. Faster Algorithms to Find Non-squares Modulo Worst-case Integers [online]. Dostupné online. (anglicky)
- ↑ Richard P. Brent; PAUL ZIMMERMANN. An O(M(n) log n) algorithm for the Jacobi symbol. [s.l.]: [s.n.], 2010. arXiv 1004.2091. (anglicky)
- ↑ P. Borwein. "On the complexity of calculating factorials". Journal of Algorithms 6, 376-380 (1985)
- ↑ Virginia Vassilevska Williams, Breaking the Coppersmith-Winograd barrier, 2011 preprint.
- ↑ J. B. Fraleigh and R. A. Beauregard, "Linear Algebra," Addison-Wesley Publishing Company, 1987, p 95.