Dokładna liczba porównań do obliczenia mediany

Tom III sztuki programowania komputerowego Knutha (rozdział 5, werset 3.2) zawiera poniższą tabelę zawierającą dokładną minimalną liczbę porównań wymaganych do wybrania tego najmniejszego elementu z nieposortowanego zestawu wielkości , dla wszystkich . Ta tabela, wraz z dobrze znanymi wyrażeniami typu zamkniętego i , reprezentuje większość stanu techniki w 1976 r. . $t$ $n$ $1\le t \le n\le 10$ $V_1(n) = n-1$ $V_2(n) = n - 2 + \lceil n/2 \rceil$

Tabela z Knuth III: 5.3.2

Czy w ciągu ostatnich 36 lat obliczono jakieś dokładniejsze wartości ? Szczególnie interesują mnie dokładne wartości , minimalna liczba porównań wymaganych do obliczenia mediany. $V_t(n)$ $M(n) = V_{\lceil n/2 \rceil}(n)$

Jak wskazuje @ MarkusBläser, tabela Knutha wydaje się już zawierać najnowsze wyniki Billa Gasarcha, Wayne'a Kelly i Billa Pugh ( Znalezienie i-tego największego spośród n dla małych i, n . SIGACT News 27 (2): 88-96, 1996 .)

ds.algorithms reference-request co.combinatorics sorting selection Jeffε
źródło

Myślę, że najbardziej znaną pracą na ten temat jest Pratt i Yao (1976), którzy są uznawani za jednych z pierwszych, którzy znaleźli jakąś (przeciwną) technikę, aby udowodnić niższe granice tego problemu. Gdybym miał znaleźć najnowsze artykuły na ten temat, śledziłbym cytaty z tego artykułu . Najnowszy artykuł to Dor i Zwick, ale jest też sondaż z 1996 roku autorstwa Patersona (choć nie szukałem, czy dotyczy to dokładnych wyników, czy nie).

Jérémie,

Nitpicking: W ostatnim zdaniu w pytaniu prawdopodobnie miałeś na myśli sufit zamiast podłogi.

Tsuyoshi Ito,

Jeff, ciekawy, dlaczego interesuje Cię dokładna odpowiedź.

Chandra Chekuri,

Kenneth Oksanen napisał wydajny kod do obliczania . Niestety jest tylko streszczenie dostępne sciencedirect.com/science/article/pii/S1571065306001582 Dwa lata temu jeden z moich studentów wysłał mu wiadomość e-mail i dostał od niego kod. Nie pamiętam, czy można uzyskać jakieś nowe wartości.

V_{i} (n)

$V_i(n)$

Markus Bläser,

@ChandraChekuri: Bawię się wariantami algorytmu wyboru czasu liniowego Blum-Floyda-Pratta-Rivesta-Tarjana jako potencjalnego problemu domowego. Jeśli użyjemy algorytmu minimalnego porównania, aby znaleźć medianę w każdym bloku, to jaki rozmiar bloku daje nam najlepszą stałą w big-Oh? 9 jest lepsze niż 7 jest lepsze niż 5; co z 11?

Jeffε

Odpowiedzi:

Kenneth Oksanen opublikował rozszerzoną tabelę wartości do w oparciu o własne wyszukiwanie komputerowe . Okansen zapewnia także opisy drzew optymalnego porównania dla większości zgłaszanych wartości. Oto zrzut ekranu jego stołu: $n=15$

Granice wyboru Kennetha Oksanena

Dzięki @ MarkusBläser za prowadzenie!

Jeffε
źródło

Zastanawiam się, czy ta informacja może ci się przydać. Niestety nie zawiera żadnych dodatkowych informacji na pytanie tego postu, ale jest raczej odpowiedzią na Twój komentarz dotyczący tego, do czego służy (analiza wariantów QuickSelect).

Oczekiwana minimalna liczba porównań, odnotowana lub jest oczywiście znacznie łatwiejsza do obliczenia (przy oczekiwaniach przyjętych jednolicie dla wszystkich permutacji), $v(n,t)$ $v_t(n)$

v_{t} (n) = n + min (t, n - t) + l.o.t. .

$v_t(n)=n+\min(t,n-t)+\text{l.o.t.}.$

Ten wynik nie jest rzadko wykorzystywany, a w szczególności stanowi podstawę algorytmów w „Adaptive Sampling for QuickSelect” autorstwa Martíneza, Panario i Violi . Punktem wyjściowym artykułu jest mediana z trzech QuickSelect, a następnie pytanie: czy istotne jest systematyczne wybieranie mediany, gdy poszukiwany element ma względną rangę znacznie niższą niż n / 2 lub znacznie wyższą niż n / 2 ?

Innymi słowy, załóżmy, że szukasz elementu na liście elementów i wybierasz sworzeń przestawny z grup elementów . Zamiast wziąć medianę ( ), weźmiesz gdzie . Pokazują, że ten algorytm może przy właściwym wyborze być praktycznie bardziej wydajny niż wariant mediany z trzech. $k$ $n$ $m$ $m/2$ $\alpha m$ $\alpha = k/n$ $m$

Jérémie
źródło