lazy.tex

\section{Lazy Select}
\sectionauthor{Krzysztof Piecuch}

\label{sec:lazy}

Naszym celem w tym rozdziale będzie znalezienie mediany w nieuporządkowanej tablicy w czasie liniowym.
Przedstawimy algorytm zrandomizowany, który albo zwróci poprawną medianę, albo stwierdzi, że poszukiwania zakończyły się fiaskiem.
Proszę mieć na uwadze fakt, że algorytm może posłużyć do znalezienia dowolnej statystyki pozycyjnej.

Mediany będziemy szukać w zbiorze $A$ i tradycyjnie załóżmy, że ma on $n$ elementów.
Ponadto oznaczmy sobie szukaną medianę jako $m$.
Na początku załóżmy, że mamy pewne dodatkowe informacje zesłane nam przez Boga, wyrocznię, wróżkę albo super-doktoranta (kto co woli).
Super-doktorant pokazuje nam dwa elementy ze zbioru $A$: $l$ oraz $u$.
Ponadto wyrocznia gwarantuje nam, że te dwa elementy mają następujące własności:
\begin{itemize}
 \item $l \leq m \leq u$
 \item $|C| \leq 4 \cdot n^{3/4} \enspace gdzie \enspace C = \{a \in A: l \leq a \leq u\}$
\end{itemize}
Czyli mediana zbioru $A$ znajduje się między podanymi elementami, oraz ilość elementów pomiędzy $l$ a $u$ jest nie większa od $4 \cdot n^{3/4}$ (elementy te oznaczamy jako zbiór $C$).
Czy z taką boską pomocą student poradzi sobie ze znalezieniem mediany w zbiorze?
Niewykluczone.
Wystarczy bowiem tylko posortować teraz elementy leżące pomiędzy $l$ a $u$.
Jeśli wybierzemy swoją ulubioną efektywną metodę sortowania, to zajmie nam to $\Theta(n^{3/4} \log n^{3/4})$ czasu.
Czyli $o(n)$ (małe $o(n)$ oznacza, że algorytm działa szybciej niż liniowo).
Następnie z posortowanego zbioru wybierzemy odpowiedni element.
W tym celu policzmy $d_l$ - liczbę elementów mniejszych od $l$ w zbiorze $A$ oraz $d_u$ - liczbę elementów większych od $u$ w zbiorze $A$.
Mediana zbioru $A$ to $n/2 - d_l + 1$-szy element posortowanego zbioru $C$.

W swoim (słynnym) skrypcie do programowania funkcyjnego Marcin Kubica napisał, że informatyka to dziedzina magii.
W ``Nowej encyklopedii powszechnej PWN'' możemy znaleźć następujące określenie magii: ``zespół działań zasadniczo pozaempirycznych, symbolicznych, których celem jest bezpośrednie osiągnięcie (...) pożądanych skutków (...)''.
Wyróżniamy przy tym następujące składniki działań magicznych:
\begin{itemize}
 \item zrytualizowane działania (manipulacje)
 \item materialne obiekty magiczne (amulety, eliksiry itp.)
 \item reguły obowiązujące przy praktykach magicznych (zasady czystości, reguły określające czas i miejsce rytuałów)
 \item formuły tekstowe mające moc sprawczą (zaklęcia)
\end{itemize}
Programowanie mieści się w ramach ostatniego z powyższych punktów.
Programy komputerowe są zapisanymi w specjalnych językach zaklęciami.
Zaklęcia te są przeznaczone dla specjalnego rodzaju duchów żyjących w komputerach, zwanymi procesami obliczeniowymi.
Ze względu na to, że komputery są obecnie produkowane seryjnie, stwierdzenie to może budzić kontrowersyjne.
Zastanówmy się jednak chwilę, czym charakteryzują się duchy.
Są to obiekty niematerialne, zdolne do działania.
Procesy obliczeniowe ewidentnie spełniają te warunki: nie można ich dotknąć, ani zobaczyć, nic nie ważą, a można obserwować skutki ich działania, czy wręcz uzyskać od nich interesujące nas informacje.
Nota bene, w trakcie zajęć można się spotkać również z przejawami pozostałych wymienionych składników działań magicznych.
``Logowanie'' się do sieci oraz wyłączanie komputera to działania o wyraźnie rytualnym charakterze.
Przedmioty takie jak indeks, czy karta zaliczeniowa wydają się mieć iście magiczną moc.

Czemu wam o tym piszę?
Bo teraz zacznie się magia :).
Jeśli bowiem nikt nam nie poda wartości $l$ oraz $u$ to będziemy musieli zabawić się we wróżkę i sami te wartości wyczarować.
Zaczniemy od utworzenia zbioru $R$ do którego zaczniemy wrzucać losowo z powtórzeniami elementy zbioru $A$ z jednakowym prawdopodobieństwem.
Będziemy robić to tak długo, aż zbiór $R$ będzie miał $n^{3/4}$ elementów.
Następnie zbiór ten posortujemy w czasie $o(n)$.
Jako wartość $l$ weźmiemy $n^{3/4}/2 - \sqrt{n}$-szy element zbioru $R$, a jako wartość $r$ weźmiemy $n^{3/4}/2 + \sqrt{n}$-szy element zbioru $R$.

\begin{algorithm}
  \DontPrintSemicolon
  \SetAlgorithmName{Algorytm}{}
  
  \KwData{ A, n }
  
  \KwResult{ m - mediana tablicy A }
  
   \For{$ i \leftarrow 0$ to $n^{3/4}$}
   {
     $R[i] \leftarrow A[random(n)]$\;
   }
   sort(R, $n^{3/4}$)\;
   $l \leftarrow R[n^{3/4}/2 - \sqrt{n}]$\;
   $u \leftarrow R[n^{3/4}/2 + \sqrt{n}]$\;
   $s \leftarrow d_l \leftarrow d_r \leftarrow 0$\;
   \For{$ i \leftarrow 0$ to $n$}
   {
     \lIf{$A[i] < l$}
     {
      $d_l \leftarrow d_l + 1$
     }
     \lElseIf{$A[i] > u$}
     {
      $d_u \leftarrow d_u + 1$
     }
     \Else
     {
      $C[s] = A[i]$\;
      $s \leftarrow s + 1$\;
     }
   }
   \lIf{$d_l > n/2$ or $d_u > n/2$ or $s > 4 * n^{3/4}$}
   {
     \Return{fail}
   }
   sort(C, $s$)\;
   \Return $C[n/2 - d_l + 1]$\;
  \caption{Procedura \texttt{lazy\_select}}
  \label{lazy-select}
\end{algorithm}

Co mogło pójść źle?
Nasze wartości $l$ oraz $u$ miały spełniać dwie własności.
Mediana miała znajdować się pomiędzy tymi wartościami oraz liczba elementów pomiędzy tymi wartościami miała być mniejsza od $4 \cdot n^{3/4}$.
Pierwszy warunek nie będzie spełniony jeśli którakolwiek z liczb $d_l$ albo $d_u$ jest większa od $n/2$.
Policzmy prawdopodobieństwo tego, że $d_l > n/2$.
Drugie prawdopodobieństwo liczy się symetrycznie.

Przez $Y$ oznaczmy sobie zbiór elementów $R$ mniejszy bądź równy medianie.
Formalnie: $Y = \{ x \in R: x \leq m\}$.
Skoro $d_l> n/2$, to $|Y| < n^{3/4}/2 - \sqrt{n}$.
Niech $X_i$ będzie zmienną losową oznaczającą, że i-ty element wybrany do zbioru $R$ był mniejszy bądź równy medianie.
Wtedy $P(X_i = 1) = E[X_i] = ((n+1)/2)/n = 1/2 + 1/2n$.
Oczywiście zmienne $X_i$ są niezależne oraz $|Y| = \sum X_i$.
Stąd łatwo możemy policzyć wartość oczekiwaną oraz wariancję $|Y|$.
\begin{align*} 
    E[|Y|] & = E\left[\sum X_i\right] = \sum E[X_i] = \frac{1}{2} \cdot n^{\frac{3}{4}} + \frac{1}{2}n^{-\frac{1}{4}} \\
    Var[X_i] & = E\left[X_i^2\right] - (E[X_i])^2 = \frac{1}{2} + \frac{1}{2 \cdot n}- (\frac{1}{2} + \frac{1}{2 \cdot n})^2 \\
             & = \frac{1}{4} - \frac{1}{4 \cdot n^2} < \frac{1}{4} \\
 Var[|Y|] & = n^{\frac{3}{4}} \cdot Var[X_i] < \frac{1}{4} \cdot n^{\frac{3}{4}}
\end{align*}
Teraz korzystając z nierówności Czebyszewa otrzymujemy interesującą nas wartość:
\begin{align*}
 P\left(fail_1\right) = & P\left(|Y| < \left(\frac{1}{2} \cdot n^{\frac{3}{4}} - \sqrt{n}\right)\right) \\
                      = & P\left(\left(\frac{1}{2} \cdot n^{\frac{3}{4}} - |Y|\right) > \sqrt{n}\right) \\
                      \leq & P\left(\left(\frac{1}{2} \cdot n^{\frac{3}{4}} + \frac{1}{2} \cdot n^{-\frac{1}{4}} - |Y|\right) > \sqrt{n}\right) \\
                      = & P\left(\left(E[|Y|] - |Y|\right) > \sqrt{n}\right)\\
                      \leq & P\left(|E[|Y|] -|Y| | > \sqrt{n}\right) \\
                      \leq & Var[|Y|] / (\sqrt{n})^2 \\
                      \leq & \frac{1}{4} \cdot n^{\frac{3}{4}} / n \\
                      = & \frac{1}{4} \cdot n^{-\frac{1}{4}}
\end{align*}

Teraz rozważymy drugą sytuację, która mogła pójść źle - zbiór $C$ okazał się za duży.
Oznacza to, że albo co najmniej $2 \cdot n^{3/4}$ elementów $C$ jest większych od mediany albo, że co najmniej $2 \cdot n^{3/4}$ elementów $C$ jest mniejszych od mediany.
Mamy zatem tak samo jak w poprzednim akapicie dwie symetryczne sytuacje.
Rozważymy pierwszą z nich.

Dowód będzie analogiczny do dowodu poprzedniego.
Przez $Y$ oznaczmy sobie zbiór elementów $R$ większych od $n/2 + 2\cdot n^{3/4}$-szego elementu zbioru $A$ (w zbiorze posortowanym).
Skoro co najmniej $2 \cdot n^{3/4}$ elementów $C$ jest większych od mediany to znaczy, że $|Y| \geq n^{3/4} - (n^{3/4}/2 + \sqrt{n}) = n^{3/4}/2 - \sqrt{n}$.
Niech $X_i$ będzie zmienną losową oznaczającą, że i-ty element wybrany do zbioru $R$ jest większy od $n/2 + 2\cdot n^{3/4}$-szego elementu zbioru $A$.
Wtedy $P(X_i = 1) = (n/2 - 2 \cdot n^{3/4}) / n = 1/2 - 2 \cdot n^{-1/4}$.
I tak jak ostatnio  $|Y| = \sum X_i$.
Teraz wartość oczekiwana oraz wariancja:
\begin{align*}
 E[|Y|] & = \frac{1}{2} \cdot n^{\frac{3}{4}} - 2 \cdot \sqrt{n} \\
 Var[|Y|] & = n^{\frac{3}{4}} Var[X_i] < \frac{1}{4} \cdot n^{\frac{3}{4}}
\end{align*}
Wykonując podobne obliczenia jak ostatnio otrzymujemy wartość:
\begin{align*}
 P\left(fail_2\right) \leq \frac{1}{4} \cdot n^{-\frac{1}{4}}
\end{align*}
Ostatecznie
\begin{align*}
 P\left(fail\right) \leq 2 \cdot P\left(fail_1\right) + 2 \cdot P\left(fail_2\right) \leq n^{-\frac{1}{4}}
\end{align*}

Otrzymaliśmy algorytm, który działa w czasie $\Theta(n)$ i zwraca poprawną medianę lub z prawdopodobieństwem mniejszym od $n^{-1/4}$ zwraca, że jej nie znalazł.