Czy możliwe jest sortowanie liczb całkowitych w O (n) w modelu transdychotomicznym?

Według mojej wiedzy nie istnieje algorytm najgorszego przypadku, który rozwiązuje następujący problem: $O(n)$

Biorąc pod uwagę ciąg długości składający się ze skończonych liczb całkowitych, znajdź permutację, w której każdy element jest mniejszy lub równy jego następcy. $n$

Ale czy istnieje dowód, że nie istnieje, w transdychotomicznym modelu obliczeniowym ?

Zauważ, że nie ograniczam zakresu liczb całkowitych. Nie ograniczam również rozwiązań do rodzajów porównawczych.

— orlp
źródło

O ile wiem, może istnieć algorytm czasowy dla SAT! Więc odpowiedź brzmi nie.

O (n)

$O(n)$

— Lembik

AFAIK, to wciąż otwarty problem.

— Juho,

Nie wiem, czy może być sensowna odpowiedź, dopóki nie określisz, jakiego modelu obliczeń używasz, biorąc pod uwagę, że nie ograniczasz komputera do porównań i zamian. Tylko w przypadku pamięci RAM i porównań dwucyfrowych argument z entropii określa limit czasu , nawet w przypadku komputerów transdhothotomicznych. Trywialnie, jeśli zamiast zamiany i porównań sortowanie jest operacją elementarną, można to zrobić w . Jeśli wstawienie liczby całkowitej w odpowiednim miejscu jest operacją podstawową, . Czy miałeś na myśli konkretny model wymiany bez porównania?

Ω (n \cdot l o g (n))

$\Omega(n\cdot log(n))$

Θ (1)

$\Theta(1)$

Θ (n)

$\Theta(n)$

— Lieuwe Vinkhuijzen,

@LieuweVinkhuijzen Moje pytanie określa transdhothotomiczny model obliczeń. W prostym języku angielskim: model obliczeniowy, w którym rozmiar słowa maszyny jest wystarczająco duży, aby pomieścić dowolną liczbę całkowitą problemu. Porównywanie dowolnych dwóch liczb całkowitych to O (1), ale także dodawanie, mnożenie itd. W tym modelu obliczeń granica entropii została już pobita, patrz Han, Yijie (2004), „Sortowanie deterministyczne w czasie O (n log log n) w przestrzeni i przestrzeni liniowej” .

— orlp

@orlp Widzę; jeśli skorzystasz ze struktury liczb całkowitych, możesz pokonać granicę entropii. Nie wiedziałem o sortowaniu liczb całkowitych; Przeczytam na ten temat!

— Lieuwe Vinkhuijzen,

Odpowiedzi:

Liczby całkowite można stabilnie sortować w czasie z dodatkową przestrzenią . $O(n)$ $O(1)$ Dokładniej, jeśli masz liczb całkowitych z zakresu , można je posortować według czasu O (n). $n$ $[1, n^c]$

Zostało to pokazane zaledwie kilka lat temu przez zespół, w tym zmarłego Mihai Pătrașcu (co nie powinno dziwić nikomu, kto jest zaznajomiony z jego pracą). To niezwykły wynik, co mnie dziwi, że więcej osób nie wie, ponieważ oznacza to, że problem sortowania liczb całkowitych został (teoretycznie) rozwiązany.

Istnieje praktyczny algorytm (podany w powyższym artykule), jeśli możesz modyfikować klucze. Zasadniczo możesz kompresować posortowane liczby całkowite bardziej niż kompresować nieposortowane liczby całkowite, a dodatkowa przestrzeń, którą zyskujesz, jest dokładnie równa dodatkowej pamięci potrzebnej do sortowania radix. Dają także niepraktyczny algorytm, który obsługuje klucze tylko do odczytu.

— Pseudonim
źródło

Z tego, co rozumiem ze streszczenia, nie jest to ogólne - może jedynie sortować słowa do wielkości w . Moje pytanie wyraźnie wymienia nieograniczone liczby całkowite.

\log n

$\log n$

O (n)

$O(n)$

— orlp

@orlp Trzeci algorytm w artykule mówi o liczbach całkowitych o nieograniczonej długości.

— pseudonim

Być może źle go czytam, ale widzę tylko opis metody zmniejszającej wykorzystanie pamięci przez nieograniczone algorytmy sortowania liczb całkowitych. Cytując ze streszczenia (moje podkreślenie): „Kolejnym interesującym pytaniem jest przypadek arbitralny $c$ . Tutaj przedstawiamy transformację czarnej skrzynki z dowolnego algorytmu sortowania pamięci RAM na algorytm sortowania, który wykorzystuje tylko dodatkową przestrzeń O (1) i ma ten sam czas działania . ”

— lub

Wybacz mi, ale w obecnym stanie ta odpowiedź w ogóle nie odpowiada na pytanie . I wyraźnie zaznaczyć, że liczby całkowite są nie ograniczone . Ta odpowiedź rozwiązuje zupełnie inny problem.

— lub

Ostatni punkt nie jest już

— pisany

-1

W przypadku liczb całkowitych można użyć sortowania Radix . Tworzy wiadra, a następnie sortuje listę liczb $O(bn)$ gdzie $b$ jest górną granicą rozmiaru w bitach dowolnej liczby całkowitej, oraz $n$ liczba elementów do posortowania.

Jeśli nie ma górnej granicy wielkości liczb całkowitych, nie sądzę, że istnieje znany algorytm sortowania w czasie liniowym.

— RFC 2549
źródło

Witamy! To, co mówisz, jest całkowicie prawdziwe, ale nie sądzę, że odpowiada na pytanie. Pytanie dotyczy konkretnie dowodu, że wymagany algorytm nie istnieje w danym modelu obliczeniowym; samo stwierdzenie, że żaden taki algorytm nie jest znany, nie dowodzi, że nie istnieje.

— David Richerby

Właściwie, b jako stały w naszym problemie, uważam ten algorytm za o (n)

— RFC 2549

Pytanie nic nie mówi

b

$b$ być stałym. Mówi tylko, że mamy

n

$n$ liczby. Te liczby mogą być dowolnie duże. (Ponadto, to prawdopodobnie tylko literówka w twoim komentarzu, ale pamiętaj o tym

O (n)

$O(n)$ i

o (n)

$o(n)$ to dwie bardzo różne rzeczy.)

— David Richerby

Tak, zdecydowanie literówka;) w swoim pytaniu, jak przypuszczasz liczbę pasującą do słowa o długości b, staje się stała.

— RFC 2549

To nie sprawia, że długość słowa jest stała. (W przeciwnym razie nie byłoby powodu, aby zakładać, wyraźnie „że operacje na pojedynczych słowach podjęcia stałej pracy na czas.”