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 $M(n)$ 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ě	O($n\cdot 2^{\sqrt {2\log n}}\log n$)
			Schönhageův–Strassenův algoritmus	O(n log n log log n)
			Fürerův algoritmus	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	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í	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, ${\sqrt {2}}$	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	O(n2/ log n)
			Stehlého–Zimmermannův algoritmus	O(log n M(n))
			Schönhageho kontrolovaný eukleidovský sestup	O(log n M(n))
Jacobiho symbol	Dvě čísla o n číslicích	0, −1, or 1
			Schönhageho kontrolovaný eukleidovský sestup	O(log n M(n))
			Stehlého–Zimmermannův algoritmus	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)), 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	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)

Reference

V tomto článku byl použit překlad textu z článku Computational complexity of mathematical operations na anglické Wikipedii.