Výpočetní složitost matematických operací

Technology

12 hours ago

Author

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)
násobení	dvě čísla o n číslicích	číslo o 2n číslicích	Karacubův algoritmus	O(n1,585)
násobení	dvě čísla o n číslicích	číslo o 2n číslicích	trojcestné Toomovo-Cookovo násobení	O(n1,465)
násobení	dvě čísla o n číslicích	číslo o 2n číslicích	k-cestné Toomovo-Cookovo násobení	O(nlog (2k − 1)/log k)
násobení	dvě čísla o n číslicích	číslo o 2n číslicích	Toomovo-Cookovo násobení smíšené úrovně	O(n\cdot 2^\sqrt{2 \log n}\log n)
násobení	dvě čísla o n číslicích	číslo o 2n číslicích	Schönhageův-Strassenův algoritmus	O(n log n log log n)
násobení	dvě čísla o n číslicích	číslo o 2n číslicích	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)
dělení	dvě čísla o n číslicích	číslo o n číslicích	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))
modulární mocnění	dvě čísla až o n číslicích a jeden exponent o k číslicích	číslo o až n číslicích	dvojkové mocnění	O(k 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	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)
Vyhodnocení polynomu	Jeden polynom stupně n s pevně danou velikostí koeficientů	Jedno číslo omezené velikosti	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)
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	Rychlý Eukleidův algoritmus	O(n (log n)2 log log n)

Important

násobení

Největší společný dělitel

Schönhageho kontrolovaný eukleidovský sestup

Stehlého-Zimmermannův algoritmus

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. +more 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. +more 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))
funkce Gama	pevně dané racionální číslo	hypergeometrické řady	O((log n)2 M(n))
funkce Gama	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))
hypergeometrická funkce pFq	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))
Eulerovo číslo, e	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))
Ludolfovo číslo, π	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)
Největší společný dělitel	Dvě čísla o n číslicích	Číslo o nejvýše n číslicích	Steinův algoritmus	O(n2)
Největší společný dělitel	Dvě čísla o n číslicích	Číslo o nejvýše n číslicích	Levý/pravýk-ární Steinův algoritmus	O(n2/ log n)
Největší společný dělitel	Dvě čísla o n číslicích	Číslo o nejvýše n číslicích	Stehlého-Zimmermannův algoritmus	O(log n M(n))
Největší společný dělitel	Dvě čísla o n číslicích	Číslo o nejvýše n číslicích	Schönhageho kontrolovaný eukleidovský sestup	O(log n M(n))
Jacobiho symbol	Dvě čísla o n číslicích	0, −1, or 1
Jacobiho symbol	Dvě čísla o n číslicích	0, −1, or 1	Schönhageho kontrolovaný eukleidovský sestup	O(log n M(n))
Jacobiho symbol	Dvě čísla o n číslicích	0, −1, or 1	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)
Faktoriál	Pevně dané číslo m	Číslo o O(m log m) číslicích	Binární dělení	O(log m M(m log m))
Faktoriál	Pevně dané číslo m	Číslo o O(m log m) číslicích	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)
Násobení matic	Dvě matice rozměrů n×n	Jedna matice o rozměru n×n	Strassenův algoritmus	O(n2,807)
Násobení matic	Dvě matice rozměrů n×n	Jedna matice o rozměru n×n	Coppersmithův-Winogradův algoritmus	O(n2,376)
Násobení matic	Dvě matice rozměrů n×n	Jedna matice o rozměru n×n	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)
Inverze matice	matice o rozměrech n×n	matice o rozměrech n×n	Strassenův algoritmus	O(n2,807)
Inverze matice	matice o rozměrech n×n	matice o rozměrech n×n	Coppersmithův-Winogradův algoritmus	O(n2,376)
Inverze matice	matice o rozměrech n×n	matice o rozměrech n×n	Williamsův algoritmus	O(n2,373)
Determinant	jedna matice o rozměrech n×n	jedna hodnota	Laplaceův rozvoj	O(n. +more)
Determinant	jedna matice o rozměrech n×n	jedna hodnota	LU dekompozice	O(n3)
Determinant	jedna matice o rozměrech n×n	jedna hodnota	Bareissův algoritmus	O(n3)
Determinant	jedna matice o rozměrech n×n	jedna hodnota	Rychlé násobení matic	O(n2,373)
Zpětné dosazení	trojúhelníková matice	n řešení	Zpětné dosazení	O(n2)

Reference

Kategorie:Matematické seznamy Kategorie:Počítačová aritmetika Kategorie:Výpočtová teorie čísel