tło
Kilka lat temu, kiedy byłem studentem, otrzymaliśmy zadanie domowe z analizy zamortyzowanej. Nie udało mi się rozwiązać jednego z problemów. Poprosiłem o to w teorii porównawczej , ale nie uzyskałem zadowalającego rezultatu. Pamiętam kurs, który TA nalegał na coś, czego nie mógł udowodnić, i powiedział, że zapomniał dowodu i ... [wiesz co].
Dzisiaj przypomniałem sobie problem. Wciąż chciałem wiedzieć, więc oto jest ...
Pytanie
Czy można zaimplementować stos przy użyciu dwóch kolejek , aby operacje PUSH i POP działały w zamortyzowanym czasie O (1) ? Jeśli tak, czy możesz mi powiedzieć jak?
Uwaga: sytuacja jest dość łatwa, jeśli chcemy zaimplementować kolejkę z dwoma stosami (z odpowiednimi operacjami WYJŚCIE i WYJŚCIE ). Proszę zwrócić uwagę na różnicę.
PS: Powyższy problem nie dotyczy samej pracy domowej. Praca domowa nie wymagała żadnych dolnych granic; tylko implementacja i analiza czasu pracy.
Odpowiedzi:
Nie mam rzeczywistej odpowiedzi, ale oto kilka dowodów na to, że problem jest otwarty:
Nie wspomniano o tym w Ming Li, Luc Longpré i Paul MB Vitányi, „The power of the queue”, Structures 1986, który rozważa kilka innych blisko powiązanych symulacji
Nie wspomina o tym Martin Hühne, „Na mocy kilku kolejek”, Theor. Komp. Sci. 1993, kolejny dokument.
Nie wspomina o tym w Holger Petersen, „Stacks versus Deques”, COCOON 2001.
Burton Rosenberg, „Szybkie niedeterministyczne rozpoznawanie języków bezkontekstowych przy użyciu dwóch kolejek”, Inform. Proc. Łotysz. 1998, daje algorytm O (n log n) dwu-kolejkowy do rozpoznawania dowolnej CFL przy użyciu dwóch kolejek. Ale niedeterministyczny automat odpychający może rozpoznać świetlówki kompaktowe w czasie liniowym. Więc jeśli istniałaby symulacja stosu z dwiema kolejkami szybszymi niż O (log n) na operację, Rosenberg i jego sędziowie powinni byli o tym wiedzieć.
źródło
Odpowiedź poniżej brzmi „oszustwo”, ponieważ chociaż nie używa on żadnej przestrzeni między operacjami, same operacje mogą wykorzystywać więcej niż przestrzeń . Zobacz gdzie indziej w tym wątku, aby uzyskać odpowiedź, w której nie ma tego problemu.O ( 1 )
Chociaż nie mam odpowiedzi na dokładne pytanie, znalazłem algorytm, który działa w czas zamiastO(n). Uważam, że jest ciasno, chociaż nie mam dowodu. Jeśli już, algorytm pokazuje, że próba udowodnienia dolnej granicyO(n)jest daremna, więc może pomóc w odpowiedzi na twoje pytanie.O ( n--√) O ( n ) O ( n )
Przedstawiam dwa algorytmy, pierwszy z nich to prosty algorytm z czasem działania dla Pop, a drugi z O ( √O ( n ) czas działania Pop. Pierwszy opisuję głównie ze względu na jego prostotę, dzięki czemu drugi jest łatwiejszy do zrozumienia.O ( n--√)
Aby podać więcej szczegółów: pierwsze nie używa dodatkowej spacji, ma najgorszy przypadek (i amortyzowane) Push i najgorszy przypadek O ( n ) (i amortyzowane) Pop, ale zachowanie najgorszego przypadku nie zawsze jest wyzwalane. Ponieważ nie wykorzystuje żadnej dodatkowej przestrzeni poza dwiema kolejkami, jest nieco „lepszy” niż rozwiązanie oferowane przez Rossa Snidera.O ( 1 ) O ( n )
Drugi używa pojedynczego pola liczb całkowitych (więc dodatkowa spacja ), ma najgorszy przypadek O ( 1 ) (i zamortyzowany) Push i O ( √O ( 1 ) O ( 1 ) amortyzowany Pop. Czas jego działania jest zatem znacznie lepszy niż w przypadku „prostego” podejścia, ale wymaga on dodatkowej przestrzeni.O ( n--√)
Pierwszy algorytm
Mamy dwie kolejki: kolejkę kolejek s e c o n D . f i r s t będzie naszą „kolejką wypychającą”, podczas gdy s e c o n d będzie kolejką już w „kolejności stosów”.fairst second first second
Kod C # dla pierwszego algorytmu
Może to być dość czytelne, nawet jeśli nigdy wcześniej nie widziałeś C #. Jeśli nie wiesz, jakie są ogólne, po prostu zamień wszystkie wystąpienia „T” na „ciąg” w swoim umyśle, aby uzyskać stos ciągów.
Analiza
Oczywiście Push działa w czasie . Pop może dotykać wszystko wewnątrz F I r s t a a e C O n d stałej ilości czasu, więc mamy O ( n ) w najgorszym przypadku. Algorytm wykazuje takie zachowanie (na przykład), jeśli popycha się n elementów na stos, a następnie wielokrotnie wykonuje pojedynczą operację Push i pojedynczą operację Pop.O ( 1 ) fajar s t s e co n d O( n ) n
Drugi algorytm
Mamy dwie kolejki: kolejkę kolejek s e c o n D . f i r s t będzie naszą „kolejką wypychającą”, podczas gdy s e c o n d będzie kolejką już w „kolejności stosów”.fai r st s e c o nd fai r st s e c o nd
Jest to dostosowane wersję pierwszego algorytmu, w którym nie od razu SHUFFLE ", których zawartość w a e C O n d . Zamiast tego, jeśli f i r s t zawiera wystarczająco małą liczbę elementów w porównaniu do s e c o n d (mianowicie pierwiastek kwadratowy z liczby elementów w s e c o n d ), reorganizujemy tylko f i r s t w stosie i nie łącz gofai r s t s e c o n d fai r s t s e c o n d s e c o n d fai r s t .s e c o n d
Kod C # dla pierwszego algorytmu
Może to być dość czytelne, nawet jeśli nigdy wcześniej nie widziałeś C #. Jeśli nie wiesz, jakie są ogólne, po prostu zamień wszystkie wystąpienia „T” na „ciąg” w swoim umyśle, aby uzyskać stos ciągów.
Analiza
Oczywiście Push działa w czasie .O(1)
Pop działa w amortyzowany czas. Istnieją dwa przypadki: jeśli| first| < √O(n−−√) , a następnie tasujemyfirstw kolejności stosu wO(|first|)=O(√|first|<|second|−−−−−−−√ first czas. Jeśli| first| ≥ √O(|first|)=O(n−−√) , to musieliśmy mieć przynajmniej√|first|≥|second|−−−−−−−√ wzywa do Push. Stąd możemy tylko hit tego sprawę każdy √n−−√ połączeń z Push i Pop. Rzeczywisty czas działania dla tego przypadku wynosiO(n), więc zamortyzowany czas wynosiO( nn−−√ O(n) .O(nn√)=O(n−−√)
Ostatnia uwaga
Możliwe jest wyeliminowanie dodatkowej zmiennej kosztem zmiany Pop na operacji, poprzez reorganizację popFIrstw każdym połączeniu zamiast push wszystkie prace.O(n−−√) first
źródło
Po kilku komentarzach do mojej poprzedniej odpowiedzi stało się dla mnie jasne, że mniej więcej oszukuję: wykorzystałem dodatkową przestrzeń ( dodatkowe miejsce w drugim algorytmie) podczas wykonywania mojej metody Pop.O(n−−√)
Poniższy algorytm nie wykorzystuje żadnej dodatkowej spacji między metodami, a jedynie dodatkową przestrzeń podczas wykonywania operacji Push i Pop. Push ma O ( √O(1) amortyzowane czas pracy i pop maO(1)najgorszym przypadku (i amortyzowane) Czas trwania.O(n−−√) O(1)
Uwaga dla moderatorów: Nie jestem do końca pewien, czy moja decyzja, aby uczynić to osobną odpowiedzią, jest poprawna. Pomyślałem, że nie powinienem usuwać mojej pierwotnej odpowiedzi, ponieważ może ona nadal mieć związek z pytaniem.
Algorytm
Mamy dwie kolejki: kolejkę kolejek s e c o n D . F I r s t będzie naszym 'bufor', a e e c o n d będzie głównym 'przechowywanie'. Obie kolejki zawsze będą w „stosie”. F I r s t zawierają elementy w górnej części stosu i e e c o n D zawiera elementy na dole stosu. Rozmiar f i rfirst second first second first second będzie zawsze co najwyżej pierwiastkiem kwadratowym s e c o n d .first second
Kod C # dla pierwszego algorytmu
Ten kod powinien być dość czytelny, nawet jeśli nigdy wcześniej nie widziałeś C #. Jeśli nie wiesz, jakie są ogólne, po prostu zamień wszystkie wystąpienia „T” na „ciąg” w swoim umyśle, aby uzyskać stos ciągów.
Analiza
Oczywiście w najgorszym przypadku Pop działa w czasie .O(1)
Push działa w amortyzowany czas. Istnieją dwa przypadki: jeśli| first| < √O(n−−√) następnie Push przyjmujeO(√|first|<|second|−−−−−−−√ czas. Jeśli| first| ≥ √O(n−−√) następnie Push zajmujeO(n)czas, ale po tej operacjifirstbędzie pusty. Zajmie toO(√|first|≥|second|−−−−−−−√ O(n) first czas, zanim ponownie otrzymamy ten przypadek, więc zamortyzowany czas wynosiO( nO(n−−√) czas.O(nn√)=O(n−−√)
źródło
first.Enqueue(first.Dequeue())
. Czy coś źle wpisałeś?źródło
O ile mi wiadomo, to nowy pomysł ...
źródło
Bez korzystania z dodatkowej przestrzeni, może przy użyciu kolejki z priorytetami i zmuszania każdego nowego pusha do nadania mu większego priorytetu niż poprzedni? Nadal nie byłby to O (1).
źródło
Nie mogę zmusić kolejek do wdrożenia stosu w zamortyzowanym stałym czasie. Mogę jednak wymyślić sposób na uzyskanie dwóch kolejek w celu wdrożenia stosu w najgorszym przypadku w czasie liniowym.
Oczywiście możemy dodać kolejny kawałek stanu zewnętrznego, który mówi nam, czy ostatnia operacja była pushem czy popem. Możemy opóźnić przenoszenie wszystkiego z jednej kolejki do drugiej, dopóki nie otrzymamy dwóch operacji wypychania z rzędu. To sprawia, że operacja pop jest nieco bardziej skomplikowana. To daje nam zamortyzowaną złożoność O (1) dla operacji pop. Niestety push pozostaje liniowy.
Wszystko to działa, ponieważ za każdym razem, gdy wykonywana jest operacja wypychania, nowy element jest umieszczany na czele pustej kolejki, a pełna kolejka jest dodawana do jej końca, skutecznie odwracając elementy.
Jeśli chcesz uzyskać amortyzację operacji w stałym czasie, prawdopodobnie będziesz musiał zrobić coś mądrzejszego.
źródło
Istnieje trywialne rozwiązanie, jeśli twoja kolejka umożliwia ładowanie od przodu, która wymaga tylko jednej kolejki (a ściślej mówiąc: deque). Być może jest to rodzaj kolejki, o której myśli TA w pierwotnym pytaniu?
Bez możliwości ładowania z przodu, oto inne rozwiązanie:
Ten algorytm wymaga dwóch kolejek i dwóch wskaźników, nazwiemy je odpowiednio Q1, Q2, podstawowy i dodatkowy. Po inicjalizacji Q1 i Q2 są puste, punkty pierwotne do Q1 i drugorzędne do Q2.
Operacja PUSH jest trywialna, polega jedynie na:
Operacja POP jest nieco bardziej zaangażowana; wymaga buforowania wszystkich z wyjątkiem ostatniej pozycji kolejki podstawowej do kolejki dodatkowej, zamiany wskaźników i zwrócenia ostatniego pozostałego elementu z kolejki oryginalnej:
Sprawdzanie granic nie jest wykonywane i nie jest to O (1).
Gdy piszę to, widzę, że można to zrobić za pomocą pojedynczej kolejki za pomocą pętli for zamiast pętli while, tak jak zrobił to Alex. Tak czy inaczej, operacja PUSH to O (1), a operacja POP zmienia się w O (n).
Oto inne rozwiązanie wykorzystujące dwie kolejki i jeden wskaźnik, odpowiednio o nazwach Q1, Q2 i queue_p:
Po inicjalizacji Q1 i Q2 są puste, a kolejka_p wskazuje na Q1.
Ponownie operacja PUSH jest trywialna, ale wymaga jednego dodatkowego kroku skierowania queue_p na drugą kolejkę:
Operacja POP jest podobna do poprzedniej, ale teraz w kolejce jest n / 2 elementów, które należy obrócić:
Operacja PUSH to nadal O (1), ale teraz operacja POP to O (n / 2).
Osobiście dla tego problemu wolę pomysł zaimplementowania pojedynczej, podwójnie zakończonej kolejki (deque) i nazywanie jej stosem, kiedy chcemy.
źródło
źródło
Stos można zaimplementować przy użyciu dwóch kolejek, używając drugiej kolejki jako nadrzędnej. Kiedy przedmioty są wypychane na stos, są dodawane na końcu kolejki. Za każdym razem, gdy element jest otwierany, elementy n - 1 pierwszej kolejki muszą być przenoszone do drugiej, a pozostały element jest zwracany. klasa publiczna QueueStack wdraża IStack {private IQueue q1 = new Queue (); prywatne IQueue q2 = nowa kolejka (); public void push (E e) {q1.enqueue (e) // O (1)} public E pop (E e) {while (1 <q1.size ()) // O (n) {q2.enqueue ( q1.dequeue ()); } sw apQueues (); return q2.dequeue (); } p rivate void swapQueues () {IQueue Q = q2; q2 = q1; q1 = Q; }}
źródło