Złożoność obliczeniowa operacji matematycznych - Computational complexity of mathematical operations

Wykresy funkcji powszechnie stosowanych w analizie algorytmów, przedstawiające liczbę operacji w funkcji wielkości wejściowej dla każdej funkcji${\ Displaystyle N}$${\ Displaystyle n}$

Poniższe tabele przedstawiają złożoność obliczeniową różnych algorytmów dla 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że O dla wyjaśnienia użytej notacji.

Uwaga: Ze względu na różnorodność algorytmów mnożenia poniżej przedstawiono złożoność wybranego algorytmu mnożenia. ${\ Displaystyle M (n)}$

Funkcje arytmetyczne

Operacja	Wejście	Wyjście	Algorytm	Złożoność
Dodatek	Dwa -cyfrowy numery, a${\ Displaystyle n}$${\ Displaystyle N}$${\ Displaystyle N}$	Jeden numer -cyfrowy ${\displaystyle n+1}$	Dodatek do podręcznika z noszeniem	${\ Displaystyle \ Theta (n), \ Theta (\ log (N))}$
Odejmowanie	Dwa -cyfrowy numery, a${\ Displaystyle n}$${\ Displaystyle N}$${\ Displaystyle N}$	Jeden numer -cyfrowy ${\displaystyle n+1}$	Odejmowanie z podręcznika szkolnego z pożyczeniem	${\ Displaystyle \ Theta (n), \ Theta (\ log (N))}$
Mnożenie	Dwa -cyfrowy numery${\ Displaystyle n}$	Jeden numer -cyfrowy ${\displaystyle 2n}$	Długie mnożenie w podręczniku	${\ Displaystyle O (n ^ {2})}$
			Algorytm Karatsuby	${\ Displaystyle O (n ^ {1,585})}$
			3-drożne mnożenie Toom-Cook	${\ Displaystyle O (n ^ {1.465})}$
			${\displaystyle k}$-sposób mnożenia Toom-Cook	${\ Displaystyle O (n ^ {\ Frac {\ log (2k-1)} {\ log k}})}$
			Toom–Cook na poziomie mieszanym (Knuth 4.3.3-T)	${\ Displaystyle O (n \ 2 ^ {\ sqrt {2 \ log n}} \ \ log n)}$
			Algorytm Schönhage-Strassena	${\ Displaystyle O (n \ log n \ log \ log n)}$
			Algorytm Fürera	${\ Displaystyle O (n \ log n \ 2 ^ {2 \ log ^ {*} n})}$
			Algorytm Harveya-Hoevena	${\ Displaystyle O (n \ log n)}$
Podział	Dwa -cyfrowy numery ${\ Displaystyle n}$	Jeden numer -cyfrowy ${\ Displaystyle n}$	Długi podział w podręczniku szkolnym	${\ Displaystyle O (n ^ {2})}$
			Dywizja dziel i zwyciężaj Burnikel-Ziegler	${\ Displaystyle O (M (n) \ log n)}$
			podział Newtona-Raphsona	${\ Displaystyle O (M (n))}$
Pierwiastek kwadratowy	Jeden numer -cyfrowy ${\ Displaystyle n}$	Jeden numer -cyfrowy ${\ Displaystyle n}$	Metoda Newtona	${\ Displaystyle O (M (n))}$
Potęgowanie modułowe	Dwa -cyfrowy całkowitymi i -bitowa wykładnik ${\ Displaystyle n}$${\displaystyle k}$	Jeden -cyfrowy całkowitą ${\ Displaystyle n}$	Wielokrotne mnożenie i zmniejszanie	${\ Displaystyle O (M (n) \ 2 ^ {k})}$
			Potęgowanie przez podniesienie do kwadratu	${\ Displaystyle O (M (n) \ k)}$
			Potęgowanie z redukcją Montgomery	${\ Displaystyle O (M (n) \ k)}$

Funkcje algebraiczne

Operacja	Wejście	Wyjście	Algorytm	Złożoność
Ocena wielomianowa	Jeden wielomian stopnia ze współczynnikami o stałej wielkości ${\ Displaystyle n}$	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]}$${\displaystyle F[x]}$	Dwa wielomiany stopnia o stałych współczynnikach całkowitych ${\ Displaystyle n}$	Co najwyżej jeden wielomian stopnia ${\ Displaystyle n}$	Algorytm Euklidesa	${\ Displaystyle O (n ^ {2})}$
			Szybki algorytm Euklidesa (Lehmer)	${\ Displaystyle O (M (n) \ log n)}$

Funkcje specjalne

Wiele metod w tej sekcji jest podanych w Borwein & Borwein.

Podstawowe funkcje

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

Poniżej rozmiar odnosi się do liczby cyfr precyzji, z jaką funkcja ma być oceniana. ${\ Displaystyle n}$

Algorytm	Zastosowanie	Złożoność
seria Taylora ; wielokrotne redukowanie argumentów (np. ) i bezpośrednie sumowanie ${\ Displaystyle \ exp (2x) = [\ exp (x)] ^ {2}}$	${\displaystyle \exp ,\log,\sin ,\cos,\arctan }$	${\ Displaystyle O (M (n) n ^ {1/2})}$
seria Taylora; Przyspieszenie oparte na FFT	${\displaystyle \exp ,\log,\sin ,\cos,\arctan }$	${\ Displaystyle O (M (n) n ^ {1/3} (\ log n) ^ {2})}$
seria Taylora; dzielenie binarne + algorytm bit-burst	${\displaystyle \exp ,\log,\sin ,\cos,\arctan }$	${\ Displaystyle O (M (n) (\ log n) ^ {2})}$
Średnia arytmetyczno-geometryczna iteracji	${\displaystyle \exp ,\log,\sin ,\cos,\arctan }$	${\ Displaystyle O (M (n) \ log n)}$

Nie wiadomo, czy jest optymalna złożoność funkcji elementarnych. Najbardziej znanym ograniczeniem dolnym jest ograniczenie trywialne . ${\ Displaystyle O (M (n) \ log n)}$${\ 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 (M (n) n ^ {1/2} (\ log n) ^ {2})}$
	Stała liczba wymierna	Szeregi hipergeometryczne	${\ Displaystyle O (M (n) (\ log n) ^ {2})}$
	${\ Displaystyle m/24}$, dla liczby całkowitej. ${\ Displaystyle m}$	Średnia arytmetyczno-geometryczna iteracji	${\ Displaystyle O (M (n) \ log n)}$
Funkcja hipergeometryczna ${\ Displaystyle {} _ {p} \! F_ {q}}$	${\ Displaystyle n}$-cyfrowy numer	(Zgodnie z opisem w Borwein & Borwein)	${\ Displaystyle O (M (n) n ^ {1/2} (\ log n) ^ {2})}$
	Stała liczba wymierna	Szeregi hipergeometryczne	${\ Displaystyle O (M (n) (\ log n) ^ {2})}$

Stałe matematyczne

Ta tabela podaje złożoność obliczania przybliżeń danych stałych do poprawnych cyfr. ${\ Displaystyle n}$

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}$	Dzielenie binarne 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}$	Dzielenie binarne szeregu arctan we wzorze Machina	${\ Displaystyle O (M (n) (\ log n) ^ {2})}$
	Algorytm Gaussa-Legendre'a	${\ Displaystyle O (M (n) \ log n)}$
stała Eulera ,${\ Displaystyle \ gamma}$	Metoda Sweeneya (przybliżenie w postaci całki wykładniczej )	${\ Displaystyle O (M (n) (\ log n) ^ {2})}$

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	Dwa -cyfrowy całkowitymi ${\ Displaystyle n}$	Jedna liczba całkowita z co najwyżej cyframi ${\ Displaystyle n}$	Algorytm Euklidesa	${\ Displaystyle O (n ^ {2})}$
			Binarny algorytm GCD	${\ Displaystyle O (n ^ {2})}$
			Lewy/prawy k- arny binarny algorytm GCD	${\ Displaystyle O (n ^ {2} \ log n)}$
			Algorytm Stehlego-Zimmermanna	${\ Displaystyle O (M (n) \ log n)}$
			Algorytm zejścia Euklidesa kontrolowany przez Schönhage	${\ Displaystyle O (M (n) \ log n)}$
Symbol Jacobiego	Dwa -cyfrowy całkowitymi ${\ Displaystyle n}$	${\ Displaystyle 0}$, lub${\ Displaystyle -1}$${\ Displaystyle 1}$	Algorytm zejścia Euklidesa kontrolowany przez Schönhage	${\ Displaystyle O (M (n) \ log n)}$
			Algorytm Stehlego-Zimmermanna	${\ Displaystyle O (M (n) \ log n)}$
Factorial	Dodatnia liczba całkowita mniejsza niż ${\ Displaystyle m}$	Jeden -cyfrowy całkowitą ${\ Displaystyle O (m \ log m)}$	Mnożenie z dołu do góry	${\ Displaystyle O (M (m ^ {2}) \ log m)}$
			Dzielenie binarne	${\ 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	A -cyfrowa liczba całkowita ${\ Displaystyle n}$	Prawda czy fałsz	Test pierwszości AKS	${\ Displaystyle O (n ^ {6})}$lub , , zakładając przypuszczenie Agrawala${\ Displaystyle O (n ^ {6+ \ varepsilon})}$ ${\ Displaystyle O (n ^ {3})}$
			Potwierdzenie pierwszości krzywej eliptycznej	${\ Displaystyle O (n ^ {4+ \ varepsilon})}$ heurystycznie
			Test pierwszości Baillie-PSW	${\ Displaystyle O (n ^ {2+ \ varepsilon})}$
			Test pierwszości Millera-Rabina	${\ Displaystyle O (kn ^ {2+ \ varepsilon})}$
			Test pierwszości Solovay-Strassena	${\ Displaystyle O (kn ^ {2+ \ varepsilon})}$
Faktoryzacja liczb całkowitych	A -bitowa wejściowa liczba całkowita ${\displaystyle b}$	Zestaw czynników	Ogólny numer sita pola	${\ Displaystyle O ((1+ \ varepsilon) ^ {b})}$
			Algorytm Shora	${\ Displaystyle O (b ^ {3})}$, na komputerze kwantowym

Algebra macierzowa

Poniższe rysunki złożoności zakładają, że arytmetyka z poszczególnymi 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}$	Mnożenie macierzy w podręczniku	${\ Displaystyle O (n ^ {3})}$
			Algorytm Strassena	${\ Displaystyle O (n ^ {2,807})}$
			Algorytm Coppersmitha-Winograda ( algorytm galaktyczny )	${\ Displaystyle O (n ^ {2.376})}$
			Zoptymalizowane algorytmy podobne do CW ( algorytmy galaktyczne )	${\ Displaystyle O (n ^ {2.3728596})}$
Mnożenie macierzy	Jedna macierz i jedna macierz ${\displaystyle n\razy m}$${\displaystyle m\razy p}$	Jedna macierz ${\displaystyle n\razy p}$	Mnożenie macierzy w podręczniku	${\ Displaystyle O (nmp)}$
Mnożenie macierzy	Jedna macierz i ${\ Displaystyle n \ razy \ lceil n ^ {k} \ rceil}$ jedna matryca, dla niektórych${\ Displaystyle \ lceil n ^ {k} \ rceil \ razy n}$${\displaystyle k\geq 0}$	Jedna macierz ${\displaystyle n\razy n}$	Algorytmy podane w	${\ Displaystyle O (n ^ {\ omega (k) + \ epsilon})}$, gdzie górne granice podane są w ${\ Displaystyle \ omega (k)}$
Odwrócenie macierzy	Jedna macierz ${\displaystyle n\razy n}$	Jedna macierz ${\displaystyle n\razy n}$	Eliminacja Gaussa-Jordana	${\ Displaystyle O (n ^ {3})}$
			Algorytm Strassena	${\ Displaystyle O (n ^ {2,807})}$
			Algorytm Coppersmith-Winograd	${\ Displaystyle O (n ^ {2.376})}$
			Zoptymalizowane algorytmy podobne do CW	${\ Displaystyle O (n ^ {2.373})}$
Rozkład według wartości osobliwych	Jedna macierz ${\displaystyle m\razy n}$	Jedna macierz, jedna macierz i jedna macierz ${\displaystyle m\razy m}$ ${\displaystyle m\razy n}$ ${\displaystyle n\razy n}$	Bidiagonalizacja i algorytm QR	${\ Displaystyle O (mn ^ {2} + m ^ {2} n)}$ ( ) ${\displaystyle m\geq n}$
		Jedna macierz, jedna macierz i jedna macierz ${\displaystyle m\razy n}$ ${\displaystyle n\razy n}$ ${\displaystyle n\razy n}$	Bidiagonalizacja i algorytm QR	${\ Displaystyle O (mn ^ {2})}$ ( ) ${\displaystyle m\geq n}$
Wyznacznik	Jedna macierz ${\displaystyle n\razy n}$	Jeden numer	Ekspansja Laplace'a	${\ Displaystyle O (n!)}$
			Algorytm bez dzielenia	${\ Displaystyle O (n ^ {4})}$
			Rozkład LU	${\ Displaystyle O (n ^ {3})}$
			Algorytm Bareiss	${\ Displaystyle O (n ^ {3})}$
			Szybkie mnożenie macierzy	${\ Displaystyle O (n ^ {2.373})}$
Powrót do substytucji	Macierz trójkątna	${\ Displaystyle n}$ rozwiązania	Powrót do substytucji	${\ Displaystyle O (n ^ {2})}$

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

Przekształcenia

Algorytmy obliczania przekształceń funkcji (w szczególności przekształceń całkowych ) są szeroko stosowane we wszystkich dziedzinach matematyki, zwłaszcza 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}$	Zbiór liczb zespolonych	Szybka transformata Fouriera	${\ Displaystyle O (n \ log n)}$

Uwagi

Bibliografia

Dalsza lektura

• Brent, Richard P .; Zimmermann, Paweł (2010). Nowoczesna arytmetyka komputerowa . Wydawnictwo Uniwersytetu Cambridge. Numer ISBN 978-0-521-19469-3.
• Knutha, Donalda Erwina (1997). Sztuka programowania komputerowego. Tom 2: Algorytmy półnumeryczne (3rd ed.). Addisona-Wesleya. Numer ISBN 978-0-201-89684-8.