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 OperaceVstupVýstupAlgoritmusSložitostsčí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 algoritmusO(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ěD. Knuth. The Art of Computer Programming, Volume 2. Third Edition, Addison-Wesley 1997.O()Schönhageův–Strassenův algoritmusO(n log n log log n)Fürerův algoritmusMartin Fürer. Faster Integer Multiplication . Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11–13, 2007, pp. 55–67.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íchNewtonova metodaO(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íchopakované 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 OperaceVstupVýstupAlgoritmusSložitostVyhodnocení polynomuJeden polynom stupně n s pevně danou velikostí koeficientů Jedno číslo omezené velikostiPří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é velikostiJeden polynom stupně nejvýše nEukleidův algoritmusO(n2)Rychlý Eukleidův algoritmus http://planetmath.org/fasteuclideanalgorithmO(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.
AlgoritmusPoužitelnostSložitostTaylorova řada; přímý součet a opakovaná redukce argumentu (tj. exp(2x) = [exp(x)]2)exp, log, sin, cosO(n1/2 M(n))Taylorova řada; zrychlení pomocí rychlé Fourierovy transformaceexp, log, sin, cosO(n1/3 (log n)2 M(n))Taylorova řada; binární dělení David and Gregory Chudnovsky. Approximations and complex multiplication according to Ramanujan. Ramanujan revisited, Academic Press, 1988, pp 375–472.exp, log, sin, cosO((log n)2 M(n))iterace aritmeticko-geometrického průměru logO(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 FunkceVstupAlgoritmusSložitostfunkce Gamačíslo o n číslicíchPostupná aproximace neúplné funkce GamaO(n1/2 (log n)2 M(n))pevně dané racionální číslohypergeometrické řadyO((log n)2 M(n))m/24, m je celé čísloiterace aritmeticko-geometrického průměru O(log n M(n))hypergeometrická funkce pFqčíslo o n číslicíchO(n1/2 (log n)2 M(n))Pevně dané racionální čísloHypergeometrické řadyO((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. KonstantaAlgoritmusSložitostZlatý řez, φMetoda tečenO(M(n))druhá odmocnina ze dvou, Metoda tečenO(M(n))Eulerovo číslo, eBinární dělení Taylorových řad pro exponenciální funkciO(log n M(n))Newtonův inverz přirozeného logaritmuO(log n M(n))Ludolfovo číslo, πBinární dělení arctanové řady v Machinově vzorciO((log n)2 M(n))Salaminův–Brentův algoritmusO(log n M(n))Eulerova–Mascheroniho konstanta, γSweeneyho metodaO((log n)2 M(n))
Teorie čísel Složitosti výpočtů z teorie čísel se věnuje výpočtová teorie čísel.
OperaceVstupVýstupAlgoritmusSložitostNejvětší společný dělitelDvě čísla o n číslicíchČíslo o nejvýše n číslicíchEukleidův algoritmusO(n2)Steinův algoritmusO(n2)Levý/pravýk-ární Steinův algoritmusO(n2/ log n)Stehlého–Zimmermannův algoritmusR. Crandall & C. Pomerance. Prime Numbers – A Computational Perspective. Second Edition, Springer 2005.O(log n M(n))Schönhageho kontrolovaný eukleidovský sestupO(log n M(n))Jacobiho symbolDvě čísla o n číslicích0, −1, or 1Schönhageho kontrolovaný eukleidovský sestupO(log n M(n))Stehlého–Zimmermannův algoritmusO(log n M(n))FaktoriálPevně dané číslo mČíslo o O(m log m) číslicíchNásobení odspoduO(m2 log m)Binární děleníO(log m M(m log m))Umocňování prvočíselných dělitelů mO(log log m M(m log m)),P. Borwein. "On the complexity of calculating factorials". Journal of Algorithms 6, 376-380 (1985)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.
OperaceVstupVýstupAlgoritmusSložitostNásobení maticDvě matice rozměrů n×nJedna matice o rozměru n×nŠkolské násobeníO(n3)Strassenův algoritmusO(n2,807)Coppersmithův–Winogradův algoritmusO(n2,376)Williamsův algoritmusVirginia Vassilevska Williams, Breaking the Coppersmith-Winograd barrier, 2011 preprint.O(n2.373)Násobení maticjedna matice o rozměrech n×m a jedna matice o rozměrech m×pjedna matice o rozměru n×p Školské násobeníO(nmp)Inverze maticematice o rozměrech n×nmatice o rozměrech n×nGaussova–Jordanova eliminaceO(n3)Strassenův algoritmusO(n2,807)Coppersmithův–Winogradův algoritmusO(n2,376)Williamsův algoritmusO(n2,373)Determinantjedna matice o rozměrech n×njedna hodnotaLaplaceův rozvojO(n!)LU dekompoziceO(n3)Bareissův algoritmusO(n3)Rychlé násobení maticO(n2,373)Zpětné dosazenítrojúhelníková maticen řešeníZpětné dosazeníO(n2)J. B. Fraleigh and R. A. Beauregard, "Linear Algebra," Addison-Wesley Publishing Company, 1987, p 95.
Reference
Kategorie:Matematické seznamy Kategorie:Počítačová aritmetika Kategorie:Výpočtová teorie čísel