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$

algorithms complexity-theory algorithm-analysis time-complexity reference-question 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

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

Odpowiedzi: