ADS úlohy D - Tříděná majorita

Existuje-li majorita, pak bude v setříděné posloupnosti určitě tvořit souvislou řadu. Tedy např. v posloupnosti 7 prvků se musí majorita nacházet na těchto pozicích (od-do):

$1-4$

$2-5$

$3-6$

$4-7$
a vždy prochází přes střed (medián).
Dokázat neexistenci majority znamená vyvrátit všechny možnosti, kde se může majorita nacházet. V případě existence majority se navrhovaný algoritmus zastaví dříve.

Pro sublineární řešení se nabízí použít binární vyhledávání: vyberu prostřední prvek (přičemž mohu vyloučit i krajní prvky) a zaznamenám si jeho hodnotu - to je kandidát na majoritu.

Dále vyberu prostřední prvek z levé poloviny. Dostávám tři možnosti:

• prvek není kandidátem
• prvek je kandidátem a shoduje se s odpovídajícím prvek z pravé poloviny
• prvek je kandidátem a neshoduje se

Odpovídající prvek z pravé poloviny je ten, který se nachází na pozici

$\lceil n/2\rceil +k$ (kde

$k$ je pozice zkoumaného prvku).

První možnost znamená, že mohu ignorovat všechny prvky nalevo od něj (nebudou kandidáty).
Druhá možnost znamená, že majorita je nalezena (celkový počet prvků znát nepotřebuju).
Třetí možnost mi umožňuje ignorovat prvky napravo (do středu) od něj, také budou kandidáty.

Dostal jsem tak algoritmus binárního vyhledávání; spodní hranice je nultý (žádný) prvek, horní hranice je střed.

Algoritmus:

Vstupní prvky: pole

$P$ (idx. od nuly, ale jinde budu začínat od jedničky), délka

$n$.

1. Index středu:
   $s=\lceil n/2\rceil$ (dolní část pro vyhledávání směrem vpravo)
2. Kandidát:
   $k=P[s]$
3. $spodek=0$,
   $vrch=s$
4. Dokud neukončím:
   1. Pokud
      $spodek=vrch$: majorita neexistuje, ukonči
   2. Zkoumaný index
      $z=(spodek+vrch)/2$
   3. Pokud
      $P[z]\ne k$:
      $spodek=z$, opakuj cyklus
   4. Pokud
      $P[z+s]=k$: majorita existuje, ukonči
   5. $vrch=z$

Složitost:

Přístup na jednotlivé prvky (z pravé poloviny) je konstantní, jelikož pole musím mít uložené v paměti. Nic jiného, než pojmenované proměnné do paměti neukládám. Binární vyhledávání bude nejhůře trvat

$O(\log n)$.

Proč to nejde líp:

Jak jsem již napsal, existuje

$\lceil n/2\rceil$ posloupností, ve kterých všechny prvky musí být majoritou (pokud existuje).
Aby jakýkoli algoritmus řekl, že majorita existuje, musí taky říct, kde začíná (jak by na to jinak přišel). Naopak pro neexistující majoritu musí všechny tyto posloupnosti vyvrátit.
V důsledku toho musí jednu z polovin (kde posloupnosti začínají, nebo končí) projít "pořádně" - o všech prvcích rozhodnout, zdali jsou nebo nejsou kandidáty.

Pole rozdělím na pět částí: nekandidáti na začátku, neznámé prvky, kandidáti prvky ve středu, neznámé prvky, nekandidáti na konci. Rozdělovače označím

$a,b,c,d.$

Pokud dokážu, že každé vybrání vyloučí indexy maximálně z poloviny jedné neznámé části (a přidá ji tak k jedné známé části), znamená to, že vylučování bude trvat

$\mathrm{\Omega }({\log }_{2}n)$.

Zvolím-li

$x$ z první poloviny první neznámé části (

$x\in (a,b)$) a

$P[x]\ne k$, pak jsem vyloučil indexy začínající

$a+1,a+2\dots x$, čímž jsem vyloučil nanejvýš polovinu možností.

Zvolím-li

$x$ z druhé poloviny první neznámé části a

$P[x]=k$, pak nemusím zkoumat indexy

$x,x+1\dots b$, čímž jsem vyloučil méně než polovinu indexů.

Pro druhou část platí totéž, ale v opačném pořadí.

Budu-li tedy vědět, v jakém pořadí vybírá algoritmus prvky, mohu vždy navrhnout hloupý vstup, pro který bude platit nejlépe logaritmická složitost.

---

Poznámky bokem

Nyní je zřejmé, že pokud se některý prvek neshoduje s kandidátem, pak mohu posloupnost ořezat (symbolicky, pomocí zarážek) na tomto prvku (přičemž původní zarážky se nacházejí na pozicích

$0$ a

$n+1$).

To znamená, že bude-li ořezaná posloupnost mít

$>n/2$ prvků, majorita existuje.

Poslední otázkou je, jak rychle (a efektivně) mohu ořezávat.