Pytania otagowane jako sorting

Mając sekwencję elementów, znajdź taką permutację, aby elementy były w określonej kolejności.

2
Sortowanie przy użyciu stosów tylko do odczytu
Rozważ następujące ustawienie: daje nam stos , który zawiera n elementów.sssnnn możemy użyć stałej liczby dodatkowych stosów .O(1)O(1)O(1) 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 …
2
Klasa złożoności odpowiadająca sortowaniu
Dwie części TCS to algorytmy i złożoność. Upraszczając powiem, że algorytmy to badanie górnych granic, pokazujące, że możesz coś zrobić (przy danych ograniczonych zasobach), a złożoność polega na pokazaniu, że nie możesz tego zrobić bez minimalnych zasobów. Tak często problem algorytmiczny pojawia się w modelu decyzyjnym, aby umieścić go w …
2
Algorytm sortowania par liczb
Zadałem już to pytanie przy przepełnieniu stosu , ale może lepiej pasuje do tej witryny. Problemem jest: Mam N par liczb całkowitych bez znaku. Muszę je posortować. Wektor końcowy par należy posortować nie malejąco według pierwszej liczby w każdej parze i nieskończenie według drugiej liczby w każdej parze. Każda para …
2
Leksykograficznie minimalny rodzaj topologiczny oznaczonego DAG
Rozważmy problem, w którym jako dane wejściowe podajemy ukierunkowany wykres acykliczny , funkcję znakowania λ od V do jakiegoś zbioru L o całkowitej kolejności < L (np. Liczby całkowite) i gdzie jesteśmy proszeni o obliczyć leksykograficznie najmniejszy rodzaj topologiczny G pod względem λ . Dokładniej, A topologiczna sortowania z G …
1
Sortuje
W ostatnim przedruku https://arxiv.org/abs/1801.00776 twierdzi się, że liczb rzeczywistych można posortować w czasie O ( n √nnn i przestrzeń liniowa. Artykuł wydaje się rozsądny, chociaż nie jestem ekspertem w dziedzinie algorytmów sortowania.O(nlogn−−−−√),O(nlog⁡n),O(n \sqrt{\log n}), Jeśli jest poprawny, byłoby to, moim zdaniem, znaczące, przynajmniej teoretycznie. Przedstawienie głównego argumentu jest jednak nieco …
1
Optymalne losowe sortowanie porównania
Więc wszyscy znamy dolną granicę drzewa na podstawie najgorszego przypadku porównań wykonanych przez (deterministyczny) algorytm sortowania porównań. Nie dotyczy losowego sortowania porównań (jeśli mierzymy oczekiwane porównania dla danych wejściowych w najgorszym przypadku). Na przykład, dla , dolna granica deterministyczna wynosi pięć porównań, ale algorytm randomizowany (losowo permutuje dane wejściowe, a …
2
Czy możemy sortować bez permutacji?
Dobrze wiadomo, że permutacje sortujące według transpozycji są w , ponieważ minimalna liczba transpozycji wymagana do sortowania π ∈ S n wynosi dokładnie i n v ( π ) = { ( i , j ) ∈ [ n ] × [ n ] : i < j i π …
12 sorting 
4
znajdowanie najmniejszych k elementów w tablicy w O (k)
To interesujące pytanie znalazłem w Internecie. Biorąc pod uwagę tablicę zawierającą n liczb (bez informacji o nich), powinniśmy wstępnie przetworzyć tablicę w czasie liniowym, abyśmy mogli zwrócić k najmniejszych elementów w czasie O (k), gdy otrzymamy liczbę 1 <= k <= n Dyskutowałem o tym problemie z przyjaciółmi, ale nikt …
12 sorting 
3
Sortowanie sekwencji „tonicznych”
Mam nadzieję, że ktoś wie o tym, więc nie muszę czytać literatury ... Rozważ ciąg liczb . Pomyśl o sekwencji jako interwałach . Oczywiście, oryginalna sekwencja jest bitoniczna, jeśli jakikolwiek punkt na prawdziwej linii dźgnie co najwyżej 2 interwały. Będziemy odnosić się do sekwencji, w której punkt dźgnie w większości …
2
Odwracanie listy przy użyciu dwóch kolejek
To pytanie jest inspirowane istniejącym pytaniem, czy stos można symulować przy użyciu dwóch kolejek w zamortyzowanym czasie na operację stosu. Odpowiedź wydaje się nieznana. Oto bardziej szczegółowe pytanie, odpowiadające specjalnemu przypadkowi, w którym najpierw wykonywane są wszystkie operacje PUSH, a następnie wszystkie operacje POP. Jak skutecznie można odwrócić listę N …
2
Określanie, co można osiągnąć przez permutację elementów grupy nieprzemiennej
Ustalić skończoną grupę . Interesuje mnie następujący problem decyzyjny: dane wejściowe to niektóre elementy G z częściowym porządkiem na nich, a pytanie brzmi, czy istnieje permutacja elementów, która spełnia porządek i jest taka, że ​​skład elementów w tym porządek daje neutralny element grupy e .GGGGGGeee Formalnie problem testu GGG jest …
2
Algorytm czasu liniowego znajdowania przesuniętego maks
Załóżmy, że otrzymujemy tablicę A[1..n]A[1..n]A[1..n] zawierającą nieujemne liczby całkowite (niekoniecznie różne). BBBAAAm=maxi∈[n]B[i]+i.m=maxi∈[n]B[i]+i.m = \max_{i\in [n]} B[i]+i. Oczywistym rozwiązaniem jest sortowanie a następnie obliczanie . Daje to algorytm działający w czasie w najgorszym przypadku.AAAmmmO(nlgn)O(nlg⁡n)O(n \lg n) Czy można to zrobić lepiej? Czy możemy obliczyć czasie liniowym?mmm Moje główne pytanie to powyższe. …
1
Sortowanie ze średnią porównań
Czy istnieje algorytm sortowania oparty na porównaniu, który wykorzystuje średnie porównania ?lg(n!)+o(n)lg(n!)+o(n)\mathrm{lg}(n!)+o(n) Istnienie algorytmu porównania najgorszego przypadku jest otwartym problemem, ale średni przypadek wystarcza dla algorytmu losowego z oczekiwanym porównania dla każdego wkładu. Znaczenie polega na tym, że są to porównania o (n) z optymalnych, marnując średnio tylko o (1) …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.