Matematické Fórum

Dobrý deň,
na tejto stránke: http://www.kiwiki.info/index.php/Algori … Quick_sort
by to malo byť [mathjax]n*log(n)[/mathjax].
Ale ako sa k tomu dostali?

Ďakujem za odpoveď a ochotu.

Jinak nedávno tu někdo řešil složitost QuickSortu v průměrném případě, je to ca týden, tak stačí zapátrat.

Dobrý deň ↑ check_drummer:,
ten Qsort v priemernom prípade som tu riešil ja :).

Ďakujem za odpoveď a ochotu.

Dobrý deň ↑ check_drummer:,
ak je zložitosť n, tak to znamená, že stačí prejsť jeden krát n prvov a mám všetko utriedené.
Ak ale je zložitosť [mathjax]n\log_{}n[/mathjax], musím prejsť [mathjax]n\log_{}n[/mathjax] prvkov aby som mal všetko utriedené.
A to si neviem predstaviť.

Ďakujem za odpoveď a ochotu.

Složitost n log n znamená jen to, že se obvykle dosáhne setřídění již po log n průchodech vnějšího cyklu. Ale pro Quicksort je minimální složitost n, když se už při prvním průchodu zjistí, že data jsou již setříděná. Teda jestli si to dobře pamatuju, naposledy jsem o Quicksortu slyšel někdy v minulém tisíciletí, od té doby ho nepoužívám, protože je pomalý a složitý :D

Zdravím, doporučuji se podívat na
https://www.algoritmy.net/article/10/Quicksort

Dobrý deň všetkým,
ja som našiel takýto pomer:
[mathjax]n! \le 2^{h} \Rightarrow h \ge \log_{2}n! \approx cn \log_{2} n[/mathjax]
Kde n! je permutacia čísel v listoch a h je hĺbka stromu.

Ďakujem za odpoveď a ochotu.