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

Złożoność rodzaju ślepego?

Odpowiedzi: