Duża złożoność O podstawowych operacji arytmetycznych

Question

Co to jest złożoność Big-O dla szeroko rozpowszechnionych algorytmów podstawowych działań arytmetycznych, takich jak mnożenie, pierwiastek kwadratowy, logarytm, iloczyn skalarny i macierzowy?

Czy istnieją egzotyczne algorytmy, które są bardziej wydajne pod względem złożoności Big-O, ale nie są zbyt rozpowszechnione w praktycznych rozwiązaniach (np. Nie są implementowane w popularnych bibliotekach oprogramowania)?

Answer 1

Patrz http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations

---

matrycy produktów matryc kwadratowych:

• O (N) (metoda naiwne)
• O (N ^2,81) (Strassen's algorithm).

Istnieje także O (N ^2,38) Coppersmith–Winograd algorithm ale nie sądzę, że to szeroko rozpowszechnione ze względu na ogromny ukryty stały.

Big Int mnożenie:

• naiwnego O (n)
• szybkiej transformaty Fouriera w oparciu o: O (N log n Log n) (Schönhage–Strassen algorithm).

Istnieje również n dziennik n & middot; 2 ^{Algorytm O (log * n)} opublikowany w 2008 roku, ale był zbyt nowy, by być powszechnym.

---

Zazwyczaj metoda naiwna jest wystarczająco dobra dla normalnej wielkości wejścia.

Answer 2

Operacje nie mają złożoności, działają algorytmy. Na przykład istnieją różne algorytmy pierwiastków kwadratowych i będą one miały różną złożoność.

Answer 3

Najprościej będzie traktować najprostsze operacje jako O (1), ponieważ zazwyczaj rozmiar wejściowy jest stały (tzn. 32- lub 64-bitowy).

W normalnych warunkach platforma wykona dokładnie tę samą operację dla mnożenia, pierwiastka kwadratowego, logarytmu itp. Niezależnie od "rozmiaru" danych wejściowych (tj. Int a = 0; int b = Int32.MaxValue są obie 32-bitowe liczby całkowite).

To staje się interesujące, gdy zaczniesz patrzeć na matryce lub reprezentować dowolnie precyzyjne liczby, ale ktoś już podłączył podsumowanie wikipedii, więc nie będę się w to zagłębiał.

Po prostu nie używaj Schönhage–Strassen do pomnażania "normalnych" małych liczb. To mnie rozpłacze. Tylko dlatego, że algorytm jest O (n ) nie znaczy, że jest złe - szczególnie gdy n jest prawie zawsze 2 lub 2 .

Answer 4

Pierwiastek kwadratowy i logarytm mogą być realizowane na różne sposoby, co znacznie wpływa na złożoność (ocenianą wymaganą precyzją).

Jeśli są zaimplementowane z tablicami odnośników (i pewną interpolacją), wymaganie pamięci naprawdę eksploduje, ponieważ wymagana jest większa precyzja, ale złożoność polega na sprawdzeniu wartości w tablicy i ewentualnym zastosowaniu interpolacji.

Bardziej popularne wydają się być realizowane przez ich definicje serii. Powtarzaj lub powtarzaj stwierdzenie przez kilka rund, aż osiągniesz wymaganą dokładność. Tutaj liczba rund może być bardzo wysoka, ponieważ potrzebna jest większa precyzja, a także na same obliczenia wpływa zwiększona precyzja.

Answer 5

Jest to rodzaj algorytmu Fouriera że robi całkowitą mnożenia jak również (Schonhage-Strassen)

myślałem, że nie było to wersja algorytmu Strassena że robi nieco lepsze niż normalne całkowitą mnożenia, ale teraz, kiedy o tym myślę, to kończy się być tym samym, co proste ...

Dodawanie i odejmowanie to właściwie tylko dodawanie i odejmowanie. Podział i pierwiastek kwadratowy są prawdopodobnie interesujące ...

RÓWNIEŻ: Zwróć uwagę, że do tej pory wszyscy mówili o Arytmetyce INTEGER. Gdy przejdziesz do floats/doubles, wszystkie zakłady są wyłączone. Następnie dostajesz się do świata numerical analysis, a to jest całe pole jego własnego ...

Answer 6

Spójrz na BigInteger, na liczbach całkowitych dowolnej długości. Wszystko ma teraz koszt pod względem wielkości wejścia, który jest liczbą bitów (zwykle O(log K) bitów dla numeru K). Będę używał N dla liczby bitów poniżej. Na przykład dodawanie i odejmowanie to teraz O(N). Mnożenie jest albo O(N^2) (naiwny) lub O(n (log n)^(2+epsilon) ) z FFT.

Inne algorytmy obejmują funkcję "zasilania", która przyjmuje mnożenie O(N). (z wyjątkiem tego, że teraz każde mnożenie ma koszt!)

Istnieją również dodatkowe komplikacje dla BigDecimals, który jest dziesiętnym odpowiednikiem długości, a poza niektórymi bardziej podstawowymi operacjami, niektóre rzeczy są również bardziej interesujące (zwłaszcza jeśli chcesz dowiedzieć się, ile chcesz precyzji). Możesz rzucić okiem na implementację Javy.

Answer 7

Podział i pierwiastki kwadratowe dla ogromnej liczby bitów nie są dużo bardziej złożone niż mnożenie. W przypadku obu operacji zwykłą iterację Newtona można ułożyć w taki sposób, że iteracja Newtona ma jedynie multiplikacje. Ponieważ liczba poprawnych cyfr jest podwojona w każdym kroku, możemy po prostu podwajać dokładność obliczeń na każdym etapie.