Insert O(1) && ExtractMedian O(1)

answered Dec 10 '14

Jasmes
111 ●5 ●5

updated Dec 10 '14

Tak ta struktura muze mit uplne libovolne uskupeni, o kterem nevime vubec nic, takze argumentace s polem nebo stromem je chybna.

Pro spor uvazujme, ze takovato mnozina opravdu existuje. Vlozime do ni $n$ prvku v case $O(n)$ a pote vsechny vybereme (zase v case $O(n)$). Tim jsme dostali serazenou posloupnost $n$ prvku v case $O(n)$, coz je spor s tim, ze umime tridit pouze v $nlog(n)$.

Proc neumime tridit rychleji nez $nlog(n)$? Counting sort je preci $O(n)$

Na vstupu jsou libovolne prvky, ktere mezi sebou umime pouze porovnavat a zadne jine informace o nich nemame. Tudiz jejich setrideni je zalozeno na Compare&Exchange. Pokud zname pouze toto, neumime je rychleji setridit, nez $nlog(n)$. Proc $nlog(n)$? Predstavme si, ze mame rozhodovaci strom, kde listy jsou ruzne posloupnosti. Ruznych posloupnosti je $n!$. Vzhledem k tomu, ze rozhodovaci strom je uplny binarni strom, jeho vyska je $log_2(n!)$. Ze Stirlingovi formule plyne, ze $log(n!)$ je $\Omega(nlog(n))$.

Proc dostanu setridenou posloupnost?

Median je prvek, ktery je v polovine setridene posloupnosti. Pokud ho vyjmu, pak dalsim medianem musi byt nutne prvek o jedna nalevo nebo napravo od puvodniho medianu. Neboli pokud je $a_i$ median, tak po jeho vyjmuti je medianem prvek $a_{i-1}$ nebo $a_{i+1}$. Pro poskladani setridene posloupnosti mi tedy staci pridat novy prvek bud na zacatek, nebo na konec. To se da udelat v $O(1)$ case.