Revision history

Tak ta struktura muze mit uplne libovolne uskupeni, o kterem nevime vubec nic, takze argumentace s polem nebo stromem je podle me 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).

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

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

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)$.

EDIT Na vstupu jsou libovolne prvky, ktere mezi sebou umime pouze porovnavat. Tudiz jejich setrideni je zalozeno na compare&switch. Pokud zname pouze toto neumime je rychleji setridit, nez $nlog(n)$. ( Podrobnejsi vysvetleni http://stackoverflow.com/questions/7155285/what-are-the-rules-for-the-%CE%A9n-log-n-barrier-for-sorting-algorithms).

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)$.

EDIT

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

Na vstupu jsou libovolne prvky, ktere mezi sebou umime pouze ~~porovnavat.~~ porovnavat a zadne jine informace o nich nemame. Tudiz jejich setrideni je zalozeno na ~~compare&switch.~~ Compare&Exchange. Pokud zname pouze ~~toto~~ toto, neumime je rychleji setridit, nez $nlog(n)$. ~~( Podrobnejsi vysvetleni http://stackoverflow.com/questions/7155285/what-are-the-rules-for-the-%CE%A9n-log-n-barrier-for-sorting-algorithms).~~
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.

Revision history [back]