Select ve median of medians

Selection problem

Input: $n$ sayılık bir $A$ array'i ve bir tam sayı $k \in \{1, \dots, n\}$. Output: $A$'nın $k$-th smallest elemanı (Bilkent slaytlarındaki adıyla $k$-th order statistic).

• $k = 1$: minimum, $k = n$: maximum, $k = \lceil n/2 \rceil$: median.
• Sorting ile çözüm: MergeSort ile sort et ($O(n\log n)$), $k$-th elemanı döndür ($O(1)$). Toplam $O(n\log n)$.

Median ve selection aynı zorlukta (class prep S6)

• Selection ⇒ median: Kolay yön. Median $=$ Select$(A, n, \lceil n/2\rceil)$.
• Linear median ⇒ linear selection: Elinde $O(n)$'lik bir median algoritması varsa Select'te pivot olarak tam median'ı kullan. Her adımda array yarıya iner: $T(n) \le T(n/2) + cn = O(n)$ (Bölüm 5).

Proposition · CS161 notları Prop. 2

Minimumu bulan her deterministic algoritmanın running time'ı $\Omega(n)$'dir.

1. Doğru çalışan bir deterministic algoritma, bir $X$ input'unda $A[i]$'yi hiç okumasın. Output'u $v$ olsun.
2. $X'$ input'u: $X$'in aynısı, sadece $X'[i] = (\min X) - 1$.
3. Algoritma $X'$ üzerinde okuduğu her yerde $X$ ile aynı değerleri görür. Deterministic olduğu için aynı adımları atar ve yine $v$ döndürür.
4. Ama $X'$'in minimumu $X'[i]$, yani $v$ değil. Algoritma iki input'tan birinde yanlış cevap verir: contradiction. Demek ki her elemanı okumalı, en az $n$ adım.

Select(A, n, k) · CS161 notları Algoritma 2

Select(A, n, k):
  if n = 1: return A[1]
  p  ← ChoosePivot(A, n)
  L  ← { a ∈ A : a < p }      R ← { a ∈ A : a > p }
  if |L| = k − 1:  return p                        (durum 1)
  if |L| > k − 1:  return Select(L, |L|, k)         (durum 2)
  if |L| < k − 1:  return Select(R, |R|, k − |L| − 1)   (durum 3)

Elemanların farklı olduğunu varsayıyoruz (eşit elemanlar Bölüm 4'te). ChoosePivot şimdilik bir kara kutu: correctness'ı etkilemez, sadece running time'ı etkiler.

Yeni k neden $k - |L| - 1$?

Durum 3'te $L$'nin $|L|$ elemanı ve $p$'nin kendisi, yani $|L| + 1$ eleman, aradığımızdan küçüktür ve $R$'ye girmez. Cevabın $A$'daki rank'i $k$ ise $R$ içindeki rank'i $k - (|L| + 1)$ olur. $k - |L|$ yazarsan pivot'u saymayı unutmuş olursun.

Strong induction ispatı · CS161 notları §3.6

IH($n$): $n$ boyundaki her $A$ ve her $k \in \{1, \dots, n\}$ için Select, $A$'nın $k$-th smallest elemanını döndürür.

Base case ($n = 1$): $k = 1$ olmak zorunda, tek eleman döner. ✓

Inductive step: $i \ge 2$ olsun ve IH her $1 \le n < i$ için doğru olsun. $|A| = i$.

• Durum 1 $|L| = k - 1$: $p$'den küçük tam $k-1$ eleman var, yani $p$ $k$-th smallest. ✓
• Durum 2 $|L| > k - 1$: $k$-th smallest $L$'dedir ve $L$'nin de $k$-th smallest elemanıdır. $|L| < i$ (pivot dışarıda) ve $1 \le k \le |L|$, yani IH uygulanır. ✓
• Durum 3 $|L| < k - 1$: cevap $R$'de, rank'i $k - |L| - 1$. IH'yi uygulamadan önce kontrol: $1 \le k - |L| - 1$ (çünkü $|L| < k - 1$) ve $k - |L| - 1 \le |R|$ (çünkü bu $k \le |L| + |R| + 1 = i$ demek). $|R| < i$. ✓

Pivot'un ne olduğu hiçbir yerde kullanılmadı: Select her pivot seçimiyle doğru.

Düzeltme: üçlü partition

$L = \{a < p\}$, $E = \{a = p\}$, $G = \{a > p\}$.

• $k \le |L|$ ise Select$(L, k)$;
• $|L| < k \le |L| + |E|$ ise $p$ döndür;
• değilse Select$(G, k - |L| - |E|)$.

$[3,3,3,3]$, $k = 2$: $|E| = 4$, $0 < 2 \le 4$ ⇒ 3 döner. ✓

Kötü pivot: hep min ya da max · notlar Önerme 3, class prep S10

Her adım sadece 1 eleman atar: $T(n) = T(n-1) + \Theta(n)$. Recurrence'ı aç:

$$c_2\,\frac{n(n+1)}{2} = c_2(n + (n-1) + \dots + 1) \;\le\; T(n) \;\le\; c_1(n + (n-1) + \dots + 1) = c_1\,\frac{n(n+1)}{2}$$

İki yönden de $n^2/2$ mertebesinde: $T(n) = \Theta(n^2)$. (Bu, en kötü $k$ için geçerli. Pivot min iken $k = 1$ olsaydı ilk adımda biterdi.)

İdeal pivot: tam median · notlar Önerme 4, class prep S11

$T(n) \le T(n/2) + cn$.

• Açarak (geometric series): $cn + \tfrac{cn}{2} + \tfrac{cn}{4} + \dots \le cn \cdot \tfrac{1}{1 - 1/2} = 2cn = O(n)$.
• Master theorem: $a = 1$, $b = 2$, $d = 1$; $a < b^d$ ⇒ $O(n^d) = O(n)$.

QuickSelect (Idea #1) · class prep S12

• Worst-case: $\Theta(n^2)$. Her seferinde en kötü pivot gelebilir (Bilkent slaytı: $[1, \dots, 8]$'de $i = 8$ ararken her pivot en küçük çıkar, boy 8, 7, 6, …).
• Expected: $O(n)$, her input için. Expected value, algoritmanın kendi yazı-turaları üzerinden alınır.

Faz argümanı (CS161 L5 concept check): Faz $i$: array boyu $\big((3/4)^{i+1}n,\ (3/4)^i n\big]$ aralığında. İyi pivot gelme probability'si $\tfrac12 \pm O(1/n)$ ⇒ bir fazdaki expected recursive call sayısı $\le 2 + O(1/n)$. Fazdaki her recursive call $\le c(3/4)^i n$ iş yapar:

$$\mathbb{E}[T(n)] \le \sum_{i \ge 0} 2c\left(\tfrac34\right)^i n = 8cn = O(n).$$

ChoosePivot(A, n) · CS161 notları Algoritma 3 (Blum, Floyd, Pratt, Rivest, Tarjan 1973)

1. $A$'yı $g = \lceil n/5 \rceil$ gruba böl (sonuncusunda 5'ten az eleman olabilir).
2. Her grubu sort et, ortadakini al: median'lar kümesi $C$, $|C| = g$.
3. $p \leftarrow$ Select$(C, g, \lceil g/2 \rceil)$: median of medians.
4. $p$'yi döndür. Select partition'ı bununla yapar.

Lemma 5 · CS161 notları §3.3.1

$g = \lceil n/5 \rceil$. $x$, $g$ median'ın median'ı olduğu için $\lceil g/2 \rceil$ grubun median'ı $\le x$ (x'in kendi grubu dâhil). x'in kendi grubu ve eksik kalan son grup hariç geriye en az $\lceil g/2 \rceil - 2$ grup kalır. Bunların her biri $x$'ten küçük 3 eleman verir:

$$|R| \le (n - 1) - 3\left(\left\lceil \tfrac g2 \right\rceil - 2\right) = n + 5 - 3\left\lceil \tfrac g2 \right\rceil \le n + 5 - \tfrac{3n}{10} = \tfrac{7n}{10} + 5$$

(Son adım: $\lceil g/2 \rceil \ge g/2 \ge n/10$.) $|L|$ için hesap aynı.

• 3 nereden? Sorted 5'li grupta median ve ondan küçük 2 eleman.
• "Grupların yarısı" nereden? $x$ median of medians olduğu için median'ların yarısı ondan küçük.
• +5 nereden? İki grubu saymadık ($-2$ grup, yani $+6$) ve $x$'in kendisi ne $L$'de ne $R$'de ($-1$): $6 - 1 = 5$.

Recurrence · class prep S16 $$T(n) \le \underbrace{c_1 n}_{\text{gruplama, grup sorting, partition}} + \underbrace{T(n/5 + 1)}_{\text{Select}(C)\text{: pivot'u bulmak}} + \underbrace{T(7n/10 + 5)}_{L\text{ ya da }R\text{'ye iniş}}\qquad (n > 5)$$

Master theorem burada uygulanmaz, çünkü iki farklı boyda subproblem var. Sadeleştirilmiş $T(n) \le T(n/5) + T(7n/10) + cn$ için substitution: $T(n) \le dn$ tahmin et;

$$\tfrac{d n}{5} + \tfrac{7 d n}{10} + cn = \tfrac{9}{10}dn + cn \le dn \iff d \ge 10c.$$

$d = \max(T(1), 10c)$ ile $T(n) = O(n)$. İkinci recursive call neden $n/2$ değil de $7n/10$? Çünkü tam median yerine yaklaşığını hesapladık. Dengeden biraz kaybettik, karşılığında pivot'u hesaplanabilir hâle getirdik.

Substitution ile kontrol · CS161 L4 concept check

• 7'li: $T(n) = n + T(n/7) + T(5n/7)$. $T \le Cn$: $\tfrac{6}{7}Cn + n \le Cn \iff C \ge 7$. En küçük $C = 7$.
• 3'lü: $T(n) = n + T(n/3) + T(2n/3)$. $\tfrac13 + \tfrac23 = 1$: $Cn + n \le Cn$ hiçbir $C$ ile sağlanmaz. Her level tam $n$ iş yapar, derinlik $\log_{3/2} n$ ⇒ $\Theta(n\log n)$.
• Oranlar toplamı 1'den büyükse (class prep L3 S3) level işi büyür ve sonuç linear'dan da kötü olur.

En küçük k eleman, üç yol · class prep S19

def closest_to_median(S, k):
    n = len(S)
    m = select(S, (n + 1) // 2)              # median, O(n)
    D = [(abs(s - m), s) for s in S]         # (mesafe, değer), hepsi farklı
    t = select(D, k)                         # k-th smallest çift, O(n)
    return [s for (d, s) in D if (d, s) <= t]   # tam k eleman, O(n)