Złożoność rodzaju ślepego?

Wszyscy wiemy, że minimalną złożonością algorytmu sortowania opartego na porównaniu są porównania . Próbuję wykonać sortowanie w ciemno , tzn. Biorąc pod uwagę liczbę wyjdź z obwodu (z bramkami logicznymi, arytmetycznymi i „porównawczymi”), który sortuje listę elementów. $\Omega(n \log n)$ $n$ $n$

Wstępne obliczanie wszystkich porównań select ${n \choose 2}$ a następnie wykonywanie arytmetyki na wynikowych bitach, daje mi algorytm $\Theta(n^3)$ , jednak myślę, że dzięki zwariowanej "arytmetyki wskaźnika" myślę, że mogę uzyskać $\Theta(n^2)$ wersja.

Czy istnieje znana dolna granica dla obwodów sortujących na podstawie porównania wzdłuż podobnych linii do $n \log n$ dla algorytmu sortowania na podstawie porównania? Czy może być nawet możliwe sortowanie w ciemno w czasie $n \log n$ ?

cc.complexity-theory terminology sorting

— Bristol
źródło

Jakie masz tło? przeszukiwałeś to? np. sortownik bioniczny daje dobrą sieć o rozmiarze

O (n \cdot \log^{2} n)

$O(n\cdot {\log^2 n})$ , a czas na utworzenie odpowiedniej sieci jest co najwyżej wielkości sieci.

— Saeed,

Mam doświadczenie w kryptografii i patrzę na sortowanie tajnie udostępnianych danych, co daje pewne dość nietypowe ograniczenia względnego kosztu operacji. Zastanawiam się, czy trafiłem na przypadek krawędziowy, w którym n^2jest dolna granica, czy też nie można go sprowadzić do zwykłego - n log npo prostu sprawdzam, czy są jakieś sytuacje, w których wyższa granica, taka jak n^2już jest znana.

— Bristol

Mam na myśli tło, ponieważ tutaj ludzie próbują zadawać pytania na poziomie badawczym , więc jeśli podasz tylko bardzo naiwne podejście, oznacza to, że nie ma zbyt wielu badań za tym pytaniem, być może inne witryny są bardziej odpowiednie do tego.

— Saeed,

Myślę, że termin techniczny na tak zwane sortowanie w ciemno jest nieświadomy „ sieci sortowania ” .

— Kaveh

„Randomized Shellsort: A Simple Oblivious Sorting Algorytm” Goodricha omawia sortowanie nieświadome danych. Sieci sortujące są nieświadome danych, ale ogólnie niepraktyczne, jak rozumiem.

— jbapple
źródło

Myślę, że sortowanie bitoniczne nie jest tak niepraktyczne, ale jest . Sieć sortowania AKS jest zdecydowanie niepraktyczna.

O (n \log^{2} n)

$O(n\log^2 n)$

— David Eppstein,