Jak możemy założyć, że podstawowe operacje na liczbach wymagają stałego czasu?

73

Zwykle w algorytmach nie dbamy o porównywanie, dodawanie lub odejmowanie liczb - zakładamy, że działają one w czasie $O(1)$ . Na przykład zakładamy, że mówimy, że sortowanie na podstawie porównania to $O(n\log n)$ , ale gdy liczby są zbyt duże, aby zmieścić się w rejestrach, zwykle reprezentujemy je jako tablice, więc podstawowe operacje wymagają dodatkowych obliczeń dla elementu.

Czy istnieje dowód, że porównanie dwóch liczb (lub innych prymitywnych funkcji arytmetycznych) można wykonać w ? Jeśli nie, dlaczego mówimy, że sortowanie na podstawie porównania to ? $O(1)$ $O(n\log n)$

I napotkał ten problem, kiedy odpowiedział na pytanie SO i zdałem sobie sprawę, że mój algorytm nie jest , ponieważ prędzej czy później powinien sobie radzić z big-int, również nie było czasu algorytm pseudo wielomian, był . $O(n)$ $P$

— Raphael
źródło

3

Jeśli zamierzasz policzyć złożoność porównywania liczb, powinieneś również zapisać swoje granice złożoności pod względem wielkości bitowej danych wejściowych. Zatem biorąc pod uwagę

bitowe liczby, rozmiar bitu na wejściu wynosi

a sortowanie można wykonać za pomocą

.

N

$N$

w

$w$

n = N w

$n=Nw$

O (N w \log N) = O (n \log n)

$O(Nw \log N) = O(n \log n)$

— Sasho Nikolov

2

zasadniczo są dwa „królestwa” lub „reżimy” badania złożoności. generalnie przyjmuje się, że operacje

operacji „stałej szerokości”, co jest rozsądnym przybliżeniem dla większości języków komputerowych, które mają reprezentacje liczb o stałej szerokości, w tym dla liczb zmiennoprzecinkowych, np. 2-4 bajtów (patrz np. standardy IEEE). wtedy jest „arytmetyka dowolnej precyzji”, w której liczby mają dowolną wielkość, i jest bardziej uważne / precyzyjne badanie złożoności operacji. pierwszy kontekst dotyczy bardziej analizy stosowanej, a drugi bardziej analizy teoretycznej / abstrakcyjnej.

O (1)

$O(1)$

— vzn

75

Dla ludzi takich jak ja, którzy badają algorytmy życia, standardowym modelem obliczeń XXI wieku jest całkowita liczba pamięci RAM . Model ma dokładniej odzwierciedlać zachowanie prawdziwych komputerów niż model maszyny Turinga. Komputery w świecie rzeczywistym przetwarzają wiele bitów liczb całkowitych w stałym czasie przy użyciu równoległego sprzętu; nie dowolne liczby całkowite, ale (ponieważ rozmiary słów stale rosną z czasem) nie są też liczbami całkowitymi o stałej wielkości .

Model zależy od jednego parametru , zwanego rozmiarem słowa . Każdy adres pamięci zawiera jedną liczbę całkowitą bit lub słowo . W tym modelu wielkość wejściowa to liczba słów na wejściu, a czas działania algorytmu to liczba operacji na słowach . Standardowe operacje arytmetyczne (dodawanie, odejmowanie, mnożenie i dzielenie całkowite, pozostałość porównanie) i operacji logicznych (bitowe, i, albo XOR, zmiany, obraca się) słów wymaga razem z definicji . $w$ $w$ $n$ $O(1)$

Formalnie rozmiar słowa NIE jest stałą $w$ do celów analizy algorytmów w tym modelu. Aby model był zgodny z intuicją, wymagamy , ponieważ w przeciwnym razie nie możemy nawet zapisać liczby całkowitej w jednym słowie. Niemniej jednak w przypadku większości algorytmów nienumerycznych czas działania jest w rzeczywistości niezależny od , ponieważ algorytmy te nie dbają o binarną reprezentację ich danych wejściowych. Mergesort i heapsort działają w czasie ; mediana-z-3-szybkich biegów działa w $w \ge \log_2 n$ $n$ $w$ $O(n\log n)$ czas w najgorszym przypadku. Jednym wyjątkiem jest binarny rodzaj podstawa, która rozciąga się w czasu. $O(n^2)$ $O(nw)$

Ustawienie daje nam tradycyjny model RAM o koszcie logarytmicznym. Ale niektóre algorytmy liczb całkowitych RAM są zaprojektowane dla większych rozmiarów słów, jak algorytm sortowania liczb całkowitych w czasie liniowym Andersson i in. , co wymaga . $w = \Theta(\log n)$ $w = \Omega(\log^{2+\varepsilon} n)$

Dla wielu algorytmów, które pojawiają się w praktyce, wielkość słowo to nie tylko problem, a my możemy (i robią) spadnie z powrotem na znacznie prostszą jednolity kosztach modelu RAM. Jedyna poważna trudność pochodzi z zagnieżdżonego mnożenia, które mogą być wykorzystane do budowy bardzo dużych liczb całkowitych bardzo szybko. Gdybyśmy mogli wykonywać arytmetykę na dowolnych liczbach całkowitych w stałym czasie, moglibyśmy rozwiązać każdy problem w PSPACE w czasie wielomianowym . $w$

Aktualizacja: Powinienem również wspomnieć, że istnieją wyjątki od „modelu standardowego”, takiego jak algorytm mnożenia liczb całkowitych Fürera , który wykorzystuje maszyny Turinga na wielu taśmach (lub równoważnie „bitowa pamięć RAM”) oraz większość algorytmów geometrycznych, które są analizowane teoretycznie czysty, ale wyidealizowany model „prawdziwej pamięci RAM” .

Tak, to puszka robaków.

— JeffE
źródło

3

Wiem, że mam po prostu głosować, ale nie mogę powstrzymać się od powiedzenia: To najlepsza odpowiedź. Sztuczka polega na tym, że (1) operacje arytmetyczne są z definicji stałym czasem i jest to w porządku, ponieważ teoretycznie możesz wybrać dowolny model, i (2) powinieneś mieć pewne powody, aby wybrać określony model, a ta odpowiedź wyjaśnia, czym one są.

— rgrig

Zgadzam się z rgig (mam też po prostu głosować), ale mały problem polega na tym, że rozmiar danych wejściowych nie jest związany z liczbami wejściowymi, np. Jeśli mam wejście

moja największa liczba to

, a jeśli wybiorę model obliczeniowy tak jak lubię, powoduje to, że algorytm pseudo wielomianowy stał się

, mam rację?

n

$n$

m

$m$

P

$P$

1

Jeśli twoje dane wejściowe składają się z liczb o więcej niż

bitach, to aby dopasować model, musisz podzielić je na części

bit, tak jak w prawdziwym życiu. Na przykład, jeśli twoje wejście składa się z

liczb całkowitych od

do

, to twój prawdziwy rozmiar wejścia to

w

$w$

w

$w$

N

$N$

0

$0$

M

$M$

. Zatem czasy działania pseudo-wielomianów, takie jak czas

są nadal wykładnicze w wielkości wejściowej, gdy

jest duże.

N \log_{w} M = (N \lg M) / (\lg w)

$N\log_w M = (N\lg M)/(\lg w)$

O (N M)

$O(NM)$

M

$M$

— JeffE

Czy istnieją jakieś algorytmy analizowane w modelu Real RAM, które nie są potajemnie algorytmami „Order Type RAM”? Nigdy o tym nie myślałem, ale nie mogę szybko wymyślić takiego przykładu.

— Louis

1

@Louis: Tak, wiele: diagramy Voronoi, najkrótsze ścieżki euklidesowe, rekurencyjne sadzonki, proste drzewa partycji ... Ale najlepszym przykładem jest eliminacja Gaussa, która działa w czasie

na rzeczywistym modelu RAM (lub koszt całkowity RAM, ale potrzebuje

czasu na całkowitą RAM

O (n^{3})

$O(n^3)$

O (n^{4})

$O(n^4)$

— JeffE

24

To zależy tylko od kontekstu. Kiedy mamy do czynienia ze złożonością algorytmów na poziomie bitów , nie mówimy, że dodanie dwóch liczb bitów jest $n$ , mówimy, że jest to . Podobnie domnożeniaitp. $O(1)$ $O(n)$

— Massimo Cafaro
źródło

Z przywołanego artykułu: „można zmierzyć na dwa różne sposoby: jeden pod względem liczb całkowitych testowanych lub mnożonych, a drugi pod względem liczby cyfr binarnych (bitów) w tych liczbach całkowitych”, ale to nieprawda, my powinien zawsze mierzyć według wielkości danych wejściowych.

1

@ SaeedAmiri: zależy to tylko od zastosowanego kodowania. W artykule, na przykład, jeśli sygnał wejściowy jest liczbą całkowitą

określono przy użyciu kodowania jednoargumentowy podział proces wymaga tylko

. Jest to wielomian wielkości wejścia! Czy to oznacza, że faktoring według podziału próby jest w

? Nie, algorytm jest pseudo-wielomianowy . Stosując wspólne kodowanie binarne, otrzymujesz algorytm wykładniczy, ponownie o wielkości wejściowej. Jak stwierdzono, dzieje się tak, ponieważ liczba bitów na wejściu

stała się wykładniczo mniejsza, zmieniając jego kodowanie.

n

$n$

θ (n^{1 / 2})

$\theta(n^{1/2})$

P

$P$

n

$n$

— Massimo Cafaro

Nawiasem mówiąc, algorytmy pseudo-wielomianowe mogą być faktycznie przydatne, jeśli rząd wielkości ich parametrów w rzeczywistych przypadkach jest dość niski. Najbardziej znanym przykładem jest prawdopodobnie algorytm pseudo-wielomianowy służący do rozwiązania problemu plecaka.

— Massimo Cafaro

Najpierw powinienem wspomnieć, że twoja strona wiki, do której się odwołujesz, nie jest dobra, ponieważ nie ma żadnych dobrych referencji. Również nie wiem, dlaczego uważasz, że mówię o algorytmach pseudo-wielomianowych, może dlatego, że rozmiar wejściowy zwykle jest wąski w tych przypadkach? ale nie mówię o nich, mówię głównie o problemach w

nawet przy założeniu wielkości wejściowej, takich jak sortowanie, w każdym razie, ponieważ nie możemy oszukiwać i twierdzimy, że problem NPC jest w

Myślę, że nie powinniśmy powiedzmy, że sortowanie to

z wyjątkiem tego, że mamy formalny dowód na zignorowanie porównania.

P

$P$

P

$P$

O (n \log n)

$O(n \log n)$

Omawiam algorytmy pseudo-wielomianowe, aby skupić uwagę na wielkości danych wejściowych i pokazać, że może to być mylące. Oto inny przykład. Podane są liczbę naturalną jako wkład, np

i algorytm prowadzi do pętli, w których prowadzi

działania na czas

iteracji. Złożoność tego prostego algorytmu pętli, mierzona jako funkcja wielkości wejściowej, wynosi

. Ponieważ

n

$n$

O (1)

$O(1)$

n

$n$

O (n) = O (2^{l g n})

$O(n) = O(2^{lg n})$

l g n

$lg n$ jest wielkością wejściową, algorytm jest wykładniczy w wielkości wejściowej! Pomyśl o tym. Teraz możesz zrozumieć, co mam na myśli, mówiąc „To zależy tylko od kontekstu”.

— Massimo Cafaro

16

Aby odpowiedzieć na pytanie, jak stwierdzono: algorytmowie po prostu robią to dość często, używając modelu pamięci RAM. W celu sortowania w wielu przypadkach ludzie analizują nawet prostszy model porównawczy , który omawiam nieco więcej w powiązanej odpowiedzi.

Aby odpowiedzieć na ukryte pytanie, dlaczego to robią: Powiedziałbym, że ten model ma dość dobrą moc predykcyjną dla niektórych rodzajów algorytmów kombinatorycznych, w których wszystkie liczby są „małe” i, na prawdziwych maszynach, mieszczą się w rejestrach.

Aby odpowiedzieć na dorozumiane działania następcze dotyczące algorytmów numerycznych: Nie, zwykły stary model pamięci RAM nie jest tutaj standardem. Nawet eliminacja gaussowska może wymagać pewnej uwagi. Zazwyczaj do obliczeń rang wchodzi Schwartz Lemma (np. Sekcja 5 tutaj ). Innym kanonicznym przykładem jest analiza algorytmu elipsoidalnego, która wymaga pewnej staranności w analizie.

I wreszcie: ludzie myśleli o sortowaniu łańcuchów wcześniej , nawet ostatnio.

Aktualizacja: Problem z tym pytaniem polega na tym, że „my” i „zakładamy” nie są tak dokładnie określone. Powiedziałbym, że ludzie, którzy pracują w modelu RAM, nie robią algorytmów numerycznych ani teorii złożoności (gdzie ustalenie złożoności podziału było znanym rezultatem ).

— Louis
źródło

Hmmmm, wydaje się, że to interesująca odpowiedź ....

Czy istnieje powód, dla którego nie można w pełni odpowiedzieć na pytanie?

— Louis

7

$O(1)$ $O(1)$

python -mtimeit "$a * $b"$a $10^{\{1,2,...,66\}}$ i $b = 2*$a. (Zatrzymałem się na 66, ponieważ wtedy składnia Pythona przestaje akceptować literały całkowite i musiałbym nieco zmienić kod oceny, więc nie zrobiłem tego: p)

$10^{50}$ $\log_{10}(\tt{sys.maxint})$

— Dougal
źródło

O (n)

$O(n)$

O (n \cdot \log n \cdot \log m)

$O(n \cdot \log n \cdot \log m)$

7

$O(1)$

$O(\log M)$ $O (N \log N)$ $O (N \log N \log M)$

$M$

— Erel Segal-Halevi
źródło

O (\log m)

$O(\log m)$

O (\log n)

$O(\log n)$

m

$m$

O (l o g N)

$O(log N)$

n

$n$

n^{n^{n}}

$n^{n^n}$

Masz rację, poprawiłem swoją odpowiedź.

— Erel Segal-Halevi

4

Powiedziałbym, że zazwyczaj zakładamy operacje arytmetyczne O (1), ponieważ zwykle robimy rzeczy w kontekście 32-bitowych liczb całkowitych lub 64-bitowych liczb całkowitych lub liczb zmiennoprzecinkowych IEEE 754. O (1) jest prawdopodobnie całkiem dobrym przybliżeniem dla tego rodzaju arytmetyki.

Ale ogólnie to nie prawda. Zasadniczo potrzebny jest algorytm do dodawania, odejmowania, mnożenia i dzielenia. Obliczalność i logika Boolosa, Burgessa i Jefferiesa mi na myśl jako sposób na zrozumienie tego dowodu, jeśli chodzi o kilka różnych systemów formalnych, Funkcje Rekurencyjne i Maszyny Abacusa, przynajmniej w moim egzemplarzu z 4. edycji.

Możesz spojrzeć na warunki rachunku lambda dla odejmowania i dzielenia za pomocą cyfr liczb kościelnych, aby uzyskać łatwe do zrozumienia wyjaśnienie, dlaczego te dwie operacje nie są O (1). Nieco trudniej jest dostrzec dodawanie, mnożenie i potęgowanie, ale jest tam, jeśli weźmie się pod uwagę formę samych Kościelnych Liczb.

— Bruce Ediger
źródło