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.

complexity-theory sorting computation-models lower-bounds 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.”