Złożoność obliczeniowa operacji matematycznych

${\ displaystyle N}$$używanych$ w analizie algorytmów, przedstawiające liczbę operacji w funkcji rozmiaru wejściowego dla każdej funkcji.

Poniższe tabele przedstawiają złożoność obliczeniową różnych algorytmów typowych operacji matematycznych .

Tutaj złożoność odnosi się do złożoności czasowej wykonywania obliczeń na wielotaśmowej maszynie Turinga . Zobacz notację dużego O , aby uzyskać wyjaśnienie zastosowanej notacji.

Uwaga: Ze względu na różnorodność algorytmów mnożenia, $oznacza$ złożoność wybranego

Funkcje arytmetyczne

Ta tabela zawiera listę złożoności operacji matematycznych na liczbach całkowitych.

Operacja	Wejście	Wyjście	Algorytm	Złożoność
Dodatek	Dwie liczby -cyfrowe, $i$${\ Displaystyle N}$ { $Displaystyle N}$	Jedna cyfra ${\ displaystyle n + 1}$	Dodatek do podręcznika szkolnego z możliwością przenoszenia	${\ Displaystyle \ Theta (n), \ Theta (\ log (N))}$
Odejmowanie	Dwie liczby -cyfrowe, $i$${\ Displaystyle N}$ { $Displaystyle N}$	Jedna cyfra ${\ displaystyle n + 1}$	Odejmowanie podręcznika szkolnego z pożyczką	${\ Displaystyle \ Theta (n), \ Theta (\ log (N))}$
Mnożenie	Dwie $-cyfrowe$ _	Jedna cyfra ${\ displaystyle 2n}$	Podręcznik długiego mnożenia	${\ Displaystyle O {\ mathord {\ lewo (n ^ {2} \ prawo)}}}$
			Algorytm Karatsuby	${\ Displaystyle O {\ mathord {\ lewo (n ^ {1,585} \ prawej)}}}$
			Trójdrożne mnożenie Toom-Cook	${\ Displaystyle O {\ mathord {\ lewo (n ^ {1,465} \ prawej)}}}$
			${\ displaystyle k}$ -sposób mnożenia Tooma – Cooka	${\ Displaystyle O {\ mathord {\ lewo (n ^ {\ Frac {\ log (2k-1)} {\ log k}} \ prawej)} }}$
			Mieszany poziom Toom-Cook (Knuth 4.3.3-T)	${\ Displaystyle O {\ mathord {\ lewo (n \ 2 ^ {\ sqrt {2 \ log n}} \, \ log n \ prawej)}}}$
			Algorytm Schönhage-Strassena	${\ Displaystyle O {\ mathord {\ lewo (n \ log n \ log \ log n \ prawo)}}}$
			Algorytm Harveya-Hoevena	${\ Displaystyle O (n \ log n)}$
Dział	Dwie $-cyfrowe$ _	Jeden $_$ numer	Podręcznik długi podział	${\ Displaystyle O {\ mathord {\ lewo (n ^ {2} \ prawo)}}}$
			Burnikel – Ziegler Dywizja „dziel i rządź”.	${\ Displaystyle O (M (n) \ log n)}$
			Podział Newtona-Raphsona	${\ Displaystyle O (M (n))}$
Pierwiastek kwadratowy	Jeden $_$ numer	Jeden $_$ numer	Metoda Newtona	${\ Displaystyle O (M (n))}$
Modułowe potęgowanie	Dwie -cyfrowe liczby $całkowite$ i -bitowy wykładnik za $\ displaystyle k}$	Jedna $liczba$ całkowita	Wielokrotne mnożenie i zmniejszanie	${\ Displaystyle O {\ mathord {\ lewo (M (n) \, 2 ^ {k} \ prawej)}}}$
			Potęgowanie przez podniesienie do kwadratu	${\ Displaystyle O (M (n) \, k)}$
			Potęgowanie z redukcją Montgomery'ego	${\ Displaystyle O (M (n) \, k)}$

Funkcje algebraiczne

Operacja	Wejście	Wyjście	Algorytm	Złożoność
Ocena wielomianowa	Jeden wielomian stopnia $rozmiarze$ współczynnikami o stałym	Jeden numer o stałym rozmiarze	Ocena bezpośrednia	${\ Displaystyle \ Theta (n)}$
			Metoda Hornera	${\ Displaystyle \ Theta (n)}$
Wielomian gcd (ponad lub ${\ Displaystyle \ mathbb {Z} [x]}$ lub ${\ Displaystyle F [x]}$ )	Dwa wielomiany stopnia ze współczynnikami całkowitymi $rozmiarze$ stałym	Co najwyżej jeden wielomian stopnia ${\ displaystyle n}$	Algorytm euklidesowy	${\ Displaystyle O {\ mathord {\ lewo (n ^ {2} \ prawo)}}}$
			Szybki algorytm euklidesowy (Lehmer)	${\ Displaystyle O (M (n) \ log n)}$

Funkcje specjalne

Wiele metod w tej sekcji podano w Borwein & Borwein.

Funkcje elementarne

Funkcje elementarne są konstruowane przez komponowanie operacji arytmetycznych, funkcji wykładniczej ( ), logarytmu naturalnego ( ${\ Displaystyle \$$log}$ ), trygonometrycznych ( ${\ Displaystyle \ sin, \ cos }$ ) i ich odwrotności. Złożoność funkcji elementarnej jest równoważna złożoności jej odwrotności, ponieważ wszystkie funkcje elementarne są analityczne , a zatem odwracalne za pomocą metody Newtona. W szczególności, jeśli albo w domenie złożonej można obliczyć z pewną złożonością, to ta złożoność jest osiągalna dla wszystkich $innych$$elementarnych$

Poniżej rozmiar odnosi się do liczby cyfr precyzji, z jaką funkcja ma być $oceniana$

Algorytm	Stosowalność	Złożoność
szereg Taylora ; wielokrotna redukcja argumentów (np. ${\ Displaystyle \ exp (2x) = [\ exp (x)] ^ {2}}$ ) i bezpośrednie sumowanie	${\ Displaystyle \ exp, \ log, \ sin, \ cos, \ arctan}$	${\ Displaystyle O {\ mathord {\ lewo (M (n) n ^ {1/2} \ prawej)}}}$
szereg Taylora; Przyspieszenie oparte na FFT	${\ Displaystyle \ exp, \ log, \ sin, \ cos, \ arctan}$	${\ Displaystyle O {\ mathord {\ lewo (M (n) n ^ {1/3} (\ log n) ^ {2} \ prawo )}}}$
szereg Taylora; podział binarny + algorytm bit-burst	${\ Displaystyle \ exp, \ log, \ sin, \ cos, \ arctan}$	${\ Displaystyle O {\ mathord {\ lewo (M (n) (\ log n) ^ {2} \ prawej)}}}$
Iteracja średniej arytmetyczno-geometrycznej	${\ Displaystyle \ exp, \ log, \ sin, \ cos, \ arctan}$	${\ Displaystyle O (M (n) \ log n)}$

Nie $_$ złożoność Najbardziej znaną dolną granicą jest trywialna granica ${\ Displaystyle \ Omega}$${\ Displaystyle (M (n))}$ .

Funkcje nieelementarne

Funkcjonować	Wejście	Algorytm	Złożoność
Funkcja gamma	${\ displaystyle n}$ -cyfrowy numer	Szeregowe przybliżenie niepełnej funkcji gamma	${\ Displaystyle O {\ mathord {\ lewo (M (n) n ^ {1/2} (\ log n) ^ {2} \ prawo )}}}$
	Stała liczba wymierna	Szeregi hipergeometryczne	${\ Displaystyle O {\ mathord {\ lewo (M (n) (\ log n) ^ {2} \ prawej)}}}$
	${\ Displaystyle m/24}$ , dla ${\ Displaystyle m}$ liczby całkowitej.	Iteracja średniej arytmetyczno-geometrycznej	${\ Displaystyle O (M (n) \ log n)}$
funkcja hipergeometryczna ${\ Displaystyle {} _ {p} \! F_ {q}}$	${\ displaystyle n}$ -cyfrowy numer	(Jak opisano w Borwein & Borwein)	${\ Displaystyle O {\ mathord {\ lewo (M (n) n ^ {1/2} (\ log n) ^ {2} \ prawo )}}}$
	Stała liczba wymierna	Szeregi hipergeometryczne	${\ Displaystyle O {\ mathord {\ lewo (M (n) (\ log n) ^ {2} \ prawej)}}}$

Stałe matematyczne

$tabela$ przedstawia złożoność przybliżeń obliczeniowych podanych stałych do cyfr.

Stały	Algorytm	Złożoność
złoty podział , ${\ Displaystyle \ phi}$	Metoda Newtona	${\ Displaystyle O (M (n))}$
pierwiastek kwadratowy z 2 , ${\ Displaystyle {\ sqrt {2}}}$	Metoda Newtona	${\ Displaystyle O (M (n))}$
liczba Eulera , ${\ displaystyle e}$	Binarny podział szeregu Taylora dla funkcji wykładniczej	${\ Displaystyle O (M (n) \ log n)}$
	Inwersja Newtona logarytmu naturalnego	${\ Displaystyle O (M (n) \ log n)}$
pi , ${\ Displaystyle \ pi}$	Binarny podział szeregu arctan we wzorze Machin'a	${\ Displaystyle O {\ mathord {\ lewo (M (n) (\ log n) ^ {2} \ prawej)}}}$
	Algorytm Gaussa-Legendre'a	${\ Displaystyle O (M (n) \ log n)}$
stała Eulera , ${\ Displaystyle \ gamma}$	Metoda Sweeneya (przybliżenie całki wykładniczej )	${\ Displaystyle O {\ mathord {\ lewo (M (n) (\ log n) ^ {2} \ prawej)}}}$

Teoria liczb

Algorytmy obliczeń teoretycznych liczb są badane w obliczeniowej teorii liczb .

Operacja	Wejście	Wyjście	Algorytm	Złożoność
Największy wspólny dzielnik	Dwie $całkowite$ liczby	Jedna liczba całkowita z co $najwyżej$	Algorytm euklidesowy	${\ Displaystyle O {\ mathord {\ lewo (n ^ {2} \ prawo)}}}$
			Binarny algorytm GCD	${\ Displaystyle O {\ mathord {\ lewo (n ^ {2} \ prawo)}}}$
			Lewo/prawo k -ary binarny algorytm GCD	${\ Displaystyle O {\ mathord {\ lewo ({\ Frac {n ^ {2}} {\ log n}} \ prawej)}}}$
			Algorytm Stehlégo-Zimmermanna	${\ Displaystyle O (M (n) \ log n)}$
			Algorytm pochodzenia euklidesowego kontrolowany przez Schönhage'a	${\ Displaystyle O (M (n) \ log n)}$
Symbol Jacobiego	Dwie $całkowite$ liczby	${\ Displaystyle 0}$ , ${\ Displaystyle -1}$ lub ${\ Displaystyle 1}$	Algorytm pochodzenia euklidesowego kontrolowany przez Schönhage'a	${\ Displaystyle O (M (n) \ log n)}$
			Algorytm Stehlégo-Zimmermanna	${\ Displaystyle O (M (n) \ log n)}$
Silnia	Dodatnia liczba całkowita mniejsza niż ${\ displaystyle m}$	O ${\ Displaystyle O (m \ log m)}$ liczba całkowita	Mnożenie od dołu do góry	${\ Displaystyle O {\ mathord {\ lewo (M \ lewo (m ^ {2} \ prawo) \ log m \ prawo)}}}$
			Podział binarny	${\ Displaystyle O (M (m \ log m) \ log m)}$
			Potęgowanie czynników pierwszych ${\ displaystyle m}$	${\ Displaystyle O (M (m \ log m) \ log \ log m)}$ , ${\ Displaystyle O ( M(m\log m))}$
Test pierwszości	ZA ${\ displaystyle n}$ -cyfrowa liczba całkowita	Prawda czy fałsz	Test pierwszości AKS	${\ Displaystyle O {\ mathord {\ lewo (n ^ {6 + o (1)} \ prawo)}}}$${\ Displaystyle O (n ^ { 3})}$ , zakładając hipotezę Agrawala
			Dowód pierwszości krzywej eliptycznej	${\ Displaystyle O {\ mathord {\ lewo (n ^ {4 + \ varepsilon} \ prawej)}}}$ heurystycznie
			Test pierwszości Baillie-PSW	${\ Displaystyle O {\ mathord {\ lewo (n ^ {2 + \ varepsilon} \ prawej)}}}$
			Test pierwszości Millera-Rabina	${\ Displaystyle O {\ mathord {\ lewo (kn ^ {2 + \ varepsilon} \ prawej)}}}$
			Test pierwszości Solovaya-Strassena	${\ Displaystyle O {\ mathord {\ lewo (kn ^ {2 + \ varepsilon} \ prawej)}}}$
Faktoryzacja liczb całkowitych	ZA ${\ displaystyle b}$ -bitowa liczba całkowita wejściowa	Zestaw czynników	Ogólne sito pola liczbowego	${\ Displaystyle O {\ mathord {\ lewo ((1 + \ varepsilon) ^ {b} \ prawej)}}}$
			Algorytm Shora	${\ Displaystyle O (M (b) b)}$ na komputerze kwantowym

Algebra macierzowa

Główny artykuł: Złożoność obliczeniowa mnożenia macierzy

Poniższe liczby złożoności zakładają, że arytmetyka z pojedynczymi elementami ma złożoność O (1), tak jak ma to miejsce w przypadku arytmetyki zmiennoprzecinkowej o stałej precyzji lub operacji na polu skończonym .

Operacja	Wejście	Wyjście	Algorytm	Złożoność
Mnożenie macierzy	Dwie macierze ${\ displaystyle n \ razy n}$	Jedna macierz ${\ displaystyle n \ razy n}$	Podręcznik mnożenia macierzy	${\ Displaystyle O (n ^ {3})}$
			Algorytm Strassena	${\ Displaystyle O {\ mathord {\ lewo (n ^ {2,807} \ prawej)}}}$
			Algorytm Coppersmitha-Winograda ( algorytm galaktyczny )	${\ Displaystyle O {\ mathord {\ lewo (n ^ {2,376} \ prawej)}}}$
			Zoptymalizowane algorytmy podobne do CW ( algorytmy galaktyczne )	${\ Displaystyle O {\ mathord {\ lewo (n ^ {2,3728596} \ prawej)}}}$
Mnożenie macierzy	Jedna $m$ i jedna macierz $razy p}$	Jedna macierz ${\ displaystyle n \ razy p}$	Podręcznik mnożenia macierzy	${\ Displaystyle O (nmp)}$
Mnożenie macierzy	Jedna ${\ Displaystyle n \ razy \ lewo \ lceil n ^ {k} \ prawo \ rceil}$ i jedna macierz ${\ Displaystyle \ lewo \ lceil n ^ {k} \ prawa \ rceil \ razy n}$ macierz, dla niektórych ${\ Displaystyle k \ geq 0}$	Jedna macierz ${\ displaystyle n \ razy n}$	Algorytmy podane w	${\ Displaystyle O (n ^ {\ omega (k) + \ epsilon})} , gdzie$ podane są górne granice ${\ Displaystyle \ omega (k)}$
Inwersja macierzy	Jedna macierz ${\ displaystyle n \ razy n}$	Jedna macierz ${\ displaystyle n \ razy n}$	Eliminacja Gaussa-Jordana	${\ Displaystyle O {\ mathord {\ lewo (n ^ {3} \ prawo)}}}$
			Algorytm Strassena	${\ Displaystyle O {\ mathord {\ lewo (n ^ {2,807} \ prawej)}}}$
			Algorytm Coppersmitha-Winograda	${\ Displaystyle O {\ mathord {\ lewo (n ^ {2,376} \ prawej)}}}$
			Zoptymalizowane algorytmy podobne do CW	${\ Displaystyle O {\ mathord {\ lewo (n ^ {2,373} \ prawej)}}}$
Rozkład według wartości osobliwych	Jedna $_$ _	Jedna macierz ${\ Displaystyle m \ razy m}$$jedna$ macierz jedna macierz n $\ razy n}$	Dwudiagonalizacja i algorytm QR	${\ Displaystyle O {\ mathord {\ lewo (m ^ {2} n \ prawej)}}}$ ( ${\ Displaystyle m \ geq n}$ )
		Jedna $macierz$ , jedna macierz $razy$ jedna macierz i jedna $}$	Dwudiagonalizacja i algorytm QR	${\ Displaystyle O {\ mathord {\ lewo (mn ^ {2} \ prawej)}}}$ ( ${\ Displaystyle m \ równoważnik n}$ )
Wyznacznik	Jedna macierz ${\ displaystyle n \ razy n}$	Jeden numer	Rozwinięcie Laplace'a	${\ Displaystyle O (n!)}$
			Algorytm bez dzielenia	${\ Displaystyle O {\ mathord {\ lewo (n ^ {4} \ prawo)}}}$
			rozkład LU	${\ Displaystyle O (n ^ {3})}$
			Algorytm Bareissa	${\ Displaystyle O {\ mathord {\ lewo (n ^ {3} \ prawo)}}}$
			Szybkie mnożenie macierzy	${\ Displaystyle O {\ mathord {\ lewo (n ^ {2,373} \ prawej)}}}$
Zmiana z powrotem	Macierz trójkątna	rozwiązania ${\ displaystyle n}$	Zmiana z powrotem	${\ Displaystyle O {\ mathord {\ lewo (n ^ {2} \ prawo)}}}$

W 2005 roku Henry Cohn , Robert Kleinberg , Balázs Szegedy i Chris Umans wykazali, że każda z dwóch różnych hipotez sugerowałaby, że wykładnik mnożenia macierzy wynosi 2.

Transformuje

Algorytmy obliczania przekształceń funkcji (zwłaszcza przekształceń całkowych ) są szeroko stosowane we wszystkich dziedzinach matematyki, aw szczególności w analizie i przetwarzaniu sygnałów .

Operacja	Wejście	Wyjście	Algorytm	Złożoność
Dyskretna transformata Fouriera	Skończona sekwencja danych o rozmiarze ${\ displaystyle n}$	Zestaw liczb zespolonych	Szybka transformata Fouriera	${\ Displaystyle O (n \ log n)}$

Dalsza lektura

•   Brent, Richard P .; Zimmermann, Paweł (2010). Nowoczesna arytmetyka komputerowa . Wydawnictwo Uniwersytetu Cambridge. ISBN 978-0-521-19469-3 .
•   Knutha, Donalda Ervina (1997). Algorytmy półnumeryczne . Sztuka programowania komputerowego . Tom. 2 (wyd. 3). Addison-Wesley. ISBN 978-0-201-89684-8 .