Mając sekwencję elementów, znajdź taką permutację, aby elementy były w określonej kolejności.
Czy istnieją znane algorytmy porównywania, które nie ograniczają się do sortowania sieci, tak że każdy element jest porównywany razy?O ( logn )O(logn)O(\log n) O ile mi wiadomo, jedynym sposobem sortowania za pomocą porównania na każdym elemencie jest zbudowanie sieci sortującej AKS dla danych...
Czy ktoś zna Yijie Han , algorytm sortowania liczb całkowitych? Wynik ten pojawia się w dość krótkim artykule ( Sortowanie deterministyczne w czasie i przestrzeni liniowej . J. Alg. 50: 96–105, 2004), który zasadniczo skleja ze sobą wiele wcześniejszych wyników, z odpowiednimi adaptacje. Mój...
Czy istnieje struktura danych, która pobiera nieuporządkowaną tablicę elementów, wykonuje wstępne przetwarzanie w i odpowiada na zapytania: czy na liście jest jakiś element , każde zapytanie w najgorszym czasie ?nnnO(n)O(n)O(n)xxxO(logn)O(logn)O(\log n) Naprawdę uważam, że nie ma, dlatego mile...
Przez jakiś czas myślałem o następującym problemie i nie znalazłem rozwiązania wielomianowego. Tylko brutalne źródło. Próbowałem też zredukować problem NP-Complete bez powodzenia. Oto problem : Masz posortowany zestaw {(A1,B1),(A2,B2),…,(An,Bn)}{(A1,B1),(A2,B2),…,(An,Bn)}\{(A_1, B_1), (A_2,...
Tom III sztuki programowania komputerowego Knutha (rozdział 5, werset 3.2) zawiera poniższą tabelę zawierającą dokładną minimalną liczbę porównań wymaganych do wybrania tego najmniejszego elementu z nieposortowanego zestawu wielkości , dla wszystkich . Ta tabela, wraz z dobrze znanymi wyrażeniami...
Jednowymiarowy problem ścieżki sprzedawcy podróży jest oczywiście tym samym, co sortowanie, a zatem można go rozwiązać dokładnie przez porównanie w czasie , ale sformułowano go w taki sposób, aby przybliżenie, a także dokładne rozwiązanie ma sens. W modelu obliczeń, w którym dane wejściowe są...
Załóżmy, że chcemy posortować listę z liczb rzeczywistych. Załóżmy, że otrzymujemy czarną skrzynkę, która może natychmiast posortować liczb rzeczywistych. Ile korzyści możemy zyskać dzięki tej czarnej skrzynce?S.SS √nnnn−−√n\sqrt n Na przykład, czy możemy posortować numery za pomocą tylko wywołań...
Tło: Chao Xu opublikował kiedyś pytanie: „ Czy są znane algorytmy sortowania porównawczego, które nie ograniczają się do sieci sortujących, tak że każdy element jest porównywany razy?O ( logn )O(logn)O(\log n) ”. Wygląda na to, że trochę utknęliśmy w tym problemie; Omówiłem ten sam problem z...
Czy możliwe jest algorytmiczne testowanie, czy liczba obliczalna jest liczbą wymierną czy całkowitą? Innymi słowy, możliwe byłoby dla biblioteki, który implementuje numery obliczalne, aby zapewnić funkcje isIntegerlub isRational? Zgaduję, że nie jest to możliwe i że jest to w jakiś sposób związane...
jest zbiorem punktów na płaszczyźnie. Losowy punkt x ∉ S jest podany na tej samej płaszczyźnie. Zadanie to rozwiązać wszystkie y ∈ S przez euklidesową odległość pomiędzy x i y .SS.Sx∉Sx∉S.x \notin Sy∈Sy∈S.y \in Sxxxyyy Podejście no-mózg jest obliczenie odległości między i Y dla wszystkich y ∈ S ,...
Interesuje mnie sortowanie tablicy dodatnich wartości liczb całkowitych w czasie liniowym (w modelu pamięci RAM z jednolitą miarą kosztów, tj. Liczby całkowite mogą mieć wielkość logarytmiczną, ale przyjmuje się, że operacje arytmetyczne na nich przyjmą czas jednostkowy). Oczywiście nie jest to...
Zasada 0-1 mówi, że jeśli sieć sortująca działa dla wszystkich sekwencji 0-1, to działa dla dowolnego zestawu liczb. Czy istnieje taki, że jeśli sieć sortuje każdą sekwencję 0-1 od S, to sortuje każdą sekwencję 0-1, a wielkość S jest wielomianowa w n ?S⊂{0,1}nS⊂{0,1}nS\subset \{0,1\}^nSSSnnn Na...
Muszę przechowywać zestawy elementów typu a. Typ a jest częściowo uporządkowany, więc porównanie i może zwrócić mniejsze, większe, równe lub nieporównywalne.a 2za1za1a_1za2)za2)a_2 Jednym z problemów z tablicami skrótów jest to, że dwa równe elementy mogą być reprezentowane w różny sposób i nie...
Ja jako dane wyjściowe DAG z n wierzchołków gdzie każdy wierzchołek x dodatkowo znakowane pewnym S ( x ) ⊆ { 1 , ... , N } .GGGnnnxxxS(x)⊆{1,…,n}S(x)⊆{1,…,n}S(x) \subseteq \{1, \ldots, n\} Topologicznym rodzajem jest bijection f z wierzchołków G do { 1 , … , n } taki, że dla wszystkich x , y ,...
Próbując opracować własny algorytm sortowania, szukam optymalnego testu porównawczego, z którym mogę go porównać. W przypadku nieposortowanego uporządkowania elementów A i posortowanego uporządkowania B , jaki jest skuteczny sposób obliczenia optymalnej liczby transpozycji, które można uzyskać od A...
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...
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...
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...
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 λ ....
Mam zestaw danych, który jest liczbą obiektów ułożonych w siatkę 2D. Wiem, że mam ścisłą kolejność, rosnącą wraz z ruchem od lewej do prawej w każdym rzędzie i rosnącą od góry do dołu w każdej kolumnie. Na przykład, 1 2 3 4 6 7 5 8 9 Czy mogę ulepszyć naiwne sortowanie, aby posortować cały...