Pytania otagowane jako sorting-network

1
Algorytm sortowania, dzięki któremu każdy element jest porównywany razy i nie zależy od sieci sortującej
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(log⁡n)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 wejściowych i uruchomienie danych wejściowych w sieci …
1
Scalanie list delikatnych obiektów
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(log⁡n)O(\log n) ”. Wygląda na to, że trochę utknęliśmy w tym problemie; Omówiłem ten sam problem z Valentinem Polczukiem w 2009 …
1
Prawdopodobieństwo działania losowej sieci sortującej
Biorąc pod uwagę nnn wejścia x0,…,xn−1x0,…,xn−1x_0, \ldots, x_{n-1} , budujemy losową sieć sortująca z mmm bram poprzez iteracyjne zbieranie dwóch zmiennych xi,xjxi,xjx_i, x_j z i&lt;ji&lt;ji < j i dodanie bramę komparatora że swapy nich, jeśli xi&gt;xjxi&gt;xjx_i > x_j . Pytanie 1 : W przypadku stałej nnn , jak duża musi …
1
Prawdopodobieństwo wygenerowania pożądanej permutacji przez losowe zamiany
Interesuje mnie następujący problem. Jako dane wejściowe podano „permutację docelową” , a także uporządkowaną listę indeksów . Następnie, zaczynając od listy (tj. Permutacja tożsamości), przy każdym kroku zamieniamy element w z element, z niezależnym prawdopodobieństwem . Niech będzie prawdopodobieństwem, że jest generowany jako wynik.I 1 , ... , i m …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.