answered
2014-12-10 07:48:08 +0100
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.
A proč by to muselo být zrovna pole? Klidně to může být nějaký strom a pak vkládání je logaritmické a medián pořád O(1).
Viktor Chlumský ( 2014-12-09 20:56:38 +0100 )editA napadá tě strom, který by mohl mít medián O(1) a insert O(log n)?
Greg ( 2014-12-09 21:51:58 +0100 )editJakýkoliv samovyvažovací BVS s tím že si pamatuju kde má prostředek (a ten samozřejmě při insertu v konstantním čase posouvám).
Viktor Chlumský ( 2014-12-09 21:56:10 +0100 )edittušil jsem, že to půjde i jinak než přes pole, ale nevěděl jsem (a pořád úplně nevím) jak. I proto jsem se zeptal. Ale jak to teda dokázat? Stačí teda říct, že medián se dá nají v O(1) jen pomocí těchto dvou struktur a v ani jednom případě není insert O(1)?
Ondřej Máca ( 2014-12-09 22:53:39 +0100 )editJestli stačí říct, že znám jenom dva způsoby jak to udělat a proto samozřejmě nemůže existovat žádný lepší? Ne.
Viktor Chlumský ( 2014-12-09 22:57:50 +0100 )edit