Rozważ następujące ustawienie:
- daje nam stos , który zawiera n elementów.
- możemy użyć stałej liczby dodatkowych stosów .
- na tych stosach możemy zastosować następujące operacje:
- sprawdź, czy stos jest pusty,
- porównaj najlepsze przedmioty z dwóch stosów,
- usuń najwyższy element ze stosu,
- wydrukuj najwyższy element na stosie,
- skopiuj górny element stosu do innego stosu,
- skopiuj zawartość jednego stosu na inny stos.
Pamiętaj, że są to jedyne dozwolone operacje. Nie możemy zamieniać przedmiotów i nie wolno nam wpychać żadnego elementu na żaden stos, z wyjątkiem kopiowania górnego elementu do stosu (po czym poprzednia zawartość stosu docelowego jest odrzucana i będzie zawierać tylko skopiowany element) .
Oto algorytm do sortowania stosów za pomocą porównań :
last := empty
for i from 1 to n
min := empty
w := s
while w is not empty
if w.top > last and w.top < min
min := w.top
delete w.top
print min
last := min
Czy możemy zrobić lepiej?
Czy istnieje program, który drukuje posortowaną listę elementów w stosach, używając tylko porównań ?
ds.algorithms
sorting
Siddharth
źródło
źródło
Odpowiedzi:
Myślę, że mogę teraz zademonstrować nietrywialną dolną granicę. Chodzi o to, aby wdrożyć dowolny taki program z rodziną porównawczych programów rozgałęziających. Założenie „tylko do odczytu” oznacza, że nasza rodzina programów rozgałęziających zużywa niewiele, tj. , przestrzeni. Następnie stosujemy dolną granicę S T = Ω ( n 2 ) udowodnioną przez Borodina i in. w „Kompromisie czasoprzestrzennym dla sortowania na nieświadomych maszynach”. To daje nam n 2O(logn) S.T.= Ω ( n2)) dolnej granicy czasu.n2)/ logn
Mówiąc bardziej szczegółowo: możemy zrezygnować z operacji 5 powyżej. Mówiąc luźniej, jeśli możemy już porównać nagłówki dwóch list i wydrukować nagłówek listy, nie musimy izolować nagłówka listy w konkretnym rejestrze. Zakładając to, widzimy, że każdy rejestr w maszynie zawsze przechowuje tylko końcowy podciąg danych wejściowych.
Załóżmy, że nasz program rejestrów ma wierszy kodu i rejestrów k , X 1 , …ℓ k .X1, … , Xk
Fix . Tworzymy porównawczy program rozgałęziający dla ciągów o długości n w następujący sposób. Utwórz węzeł dla każdej krotki ( i , d 1 , … , d k ), gdzie 1 ≤ i ≤ ℓ i 0 ≤ d 1 , … , d k ≤ n . Chodzi o to, że obliczenia w maszynie rejestrującej odpowiadają ścieżkom w programie rozgałęziającym, a my jesteśmy w węźle ( i , d 1 , … , dn n ( i , d1, … , Dk) 1≤i≤ℓ 0≤d1,…,dk≤n jeśli znajdujemy się w linii iwynosi d i . Teraz musimy zdefiniować ukierunkowane krawędzie programu rozgałęziającego(i,d1,…,dk) i w maszynie rejestrującej i długość ciągu zapisanego w Xi di
Jeśli linia ma postaći
jeśli to goto i 1Xu<Xv i1 else gotoi2
następnie dla wszystkich , węzeł ( i , d 1 , … , d k ) jest oznaczony poprzez porównanie d u-tego i d v-tego elementu wejściowego, a „prawdziwa” krawędź przechodzi do ( i 1 , d 1 , … , d k ) , a „fałszywa” krawędź do ( i 2 , d 1d1,…,dk (i,d1,…,dk) du dv (i1,d1,…,dk) .(i2,d1,…,dk)
Jeśli linia ma postaći
, linia gotoX1←tail(X2) i′
następnie jest strzałka z dowolnego węzła do ( i ′ , d 2 - 1 , … , d(i,d1,…,dk) .(i′,d2−1,…,dk)
Jeśli linia ma postaći
, goto lineprint(head(Xu)) i′
Następnie znajduje się strzałka z dowolnego węzła do ( I ' , d 1 , ... , d k ) , który jest oznaczony przez D u -ty węzła wejścia.(i,d1,…,dk) (i′,d1,…,dk) du
Mam nadzieję, że te przykłady wyjaśniają, w jaki sposób zamierzam zbudować program rozgałęziający. Kiedy wszystko jest powiedziane i zrobione, ten program rozgałęzienia ma co najwyżej węzłów, a więc ma miejsce O ( log n )ℓ⋅nk O(logn)
źródło
Czy potrafisz liczyć elementy? Myślę, że wtedy jest dość łatwa implementacja Mergesort. Gdybyś był w stanie umieścić dodatkowe symbole na stosie, możesz rozwiązać go za pomocą 3 takich stosów:
Jeśli mamy tylko jeden element, lista jest już posortowana. Załóżmy teraz, że posortowaliśmy już górną połowę stosu. Możemy skopiować górną połowę (w odwrotnej kolejności) do drugiego stosu i umieścić na nim symbol separacji. Teraz znów mamy 3 stosy (ponieważ możemy zignorować już posortowane symbole poniżej symbolu separacji) i możemy posortować dolną połowę. Wreszcie możemy skopiować posortowaną dolną połowę do trzeciego stosu w odwrotnej kolejności i scalić obie połówki z powrotem do oryginalnego stosu.
Wszystkie operacje kosztują czas liniowy, dlatego posortowaliśmy listę wO(nlogn)
(Uwaga: potrzebujemy stosów o rozmiarze ze względu na symbole separacji, ale można to łatwo poprawić za pomocą innego stosu)nlogn
Ponieważ nie możesz umieścić nowych elementów na stosie, możesz mieć problemy w punktach separacji. Aby rozwiązać ten problem, możesz wykonać następujące czynności z kilkoma dodatkowymi stosami:
Skopiuj górne elementy do dodatkowego stosu, a następnie postępuj z pozostałymi elementami jak poprzednio. Teraz znasz dokładnie liczbę elementów, które musisz wziąć pod uwagę na każdym etapie, a zatem nie potrzebujesz żadnych symboli separacji.n−2⌊logn⌋
źródło