Matematické Fórum

Dobrý deň všetkým,
je zaujímavé čítať vašu diskusiu, ale nikto sa zatiaľ neviadril koľko je [mathjax]n \log_{2}n[/mathjax] prvkov. Zatiaľ ste sa len viadrili, že zložitosť n je taká, že stačí prejsť jeden krát n prvkov a ak boli prvky dopredu usporiadané tak to zistí.
Vari ak sú prvky qsortu dopredu usporiadané, tak stačí prejsť [mathjax]n \log_{2}n[/mathjax] prvkov (ak mám byť presný, tak sa jedná o porovnavanie a nie o počet prvkov).

Ďakujem za odpoveď a ochotu.

Dá se to taky brát tak, že [mathjax]log_2 n[/mathjax] je počet bitů které potřebuješ k zapsání čísla [mathjax]n[/mathjax]. Prostě při každém průchodu rozpůlíš interval a takhle to vyjde (u quicksortu za ideálních podmínek při správně zvoleném rozhodovacím prvku).

Složitost se bere že je úměrná počtu porovnání a počet porovnání se vypočítá z počtu prvků. Ty vzorečky [mathjax]n^{2}[/mathjax], [mathjax]n \log_{2}n[/mathjax] apod. říkají, kolik porovnání ten který algoritmus potřebuje k setřídění souboru. Pak by byla k diskusi ještě ta konstanta úměrnosti, což jsem zkusil nadhodit v již smazaných OT příspěvcích :-) Jednotlivé složitosti si nech nakreslit Wolframem, příkaz plot, je to názornější než tady cokoliv psát.

Ano, je to přesně takhle, vždycky je tam minimální a maximální složitost podle toho jak moc je soubor nesetříděný (ale ne vždycky se ta minimální od maximální musí lišit a ne vždycky je ta minimální rovná n). Tedy jestli jsem správně pochopil na co se ptáš :-)

Zkus tohle
https://www.wolframalpha.com/input/?i=p … om+1+to+10

fmfiain napsal(a):

Teda algoritmus Qsort môže mať v najhoršom prípade [mathjax]n^{2}[/mathjax] porovnaní a v ostatných prípadoch [mathjax]n \log_{2}n[/mathjax] porovnaní.

Podle mě i "druhý nejhorší" případ bude potřebovat [mathjax]n^{2}[/mathjax] porovnaní.
Ale pokud jde o asymptotické chování, tak to bude podle mě mezi [mathjax]n \log_{2}n[/mathjax] a [mathjax]n^{2}[/mathjax], tedy to hledané minimum bude podle mě [mathjax]n \log_{2}n[/mathjax]. Ale nevím k čemu je takové minimum dobré. Pokud bychom např. nejdřív zkontrolovali, zda je posloupnost setříděná, a pokud by byla, tak skončíme, tak by to minimum bylo n. Nebo bychom mohli pustit několik průchodů bubble sortu (nějaký pevný počet, třeba 10), a pokud by se během těch průchodů nepodařilo posloupnost utřídit, tak bychom pustili QuickSort, a i v tomto případě by byla minimální složitost n. A i tady je na místě otázka, k čemu je taková minimální složitost dobrá.
V tomto případě bych řekl, že je to spíše zajímavá akademická otázka.

Dobrý deň ↑ check_drummer:,
ako by si počítal limitu z #17: [mathjax]\lim \frac{log_2 (n!)}{cn*log_2(n)}[/mathjax]
alebo naopak: [mathjax]\lim \frac{cn*log_2(n)}{log_2 (n!)}[/mathjax].
Vôbec neviem k čomu smeruje n. A tak isto neviem, ktorá s týchto limít je ta správna.
O tom n viem iba to, že je z jednej strany ohraničené [mathjax]\ge 2[/mathjax] a z druhej strany je ohraničené [mathjax]\le \infty [/mathjax].

Ďakujem za odpoveď a ochotu.

Dobrý deň ↑ check_drummer:,
mňa napadla iba úprava: [mathjax]\lim \frac{log_2 (n!)}{cn*log_2(n)} = \lim \frac{log_2 (n!)}{log_2(n^{cn})} = 1                  [/mathjax], alebo [mathjax]\lim \frac{cn*log_2(n)}{log_2 (n!)} = \lim \frac{log_2(n^{cn})}{log_2 (n!)} = 1[/mathjax].

A keď nad tým tak rozmýšľam a výsledky limít sú rovnaké, je jedno, ktorú si vyberiem.

Ďakujem za odpoveď a ochotu.

Dobrý deň ↑ Aleš13: a ↑ check_drummer:,
ak má zmysel rátať iba vysoké n, tak potom tá limita v #42 je pre [mathjax]\lim_{n\to\infty }[/mathjax].
Mám pravdu?

Ďakujem za odpoveď a ochotu.

Dobrý deň všetkým,
skúste sa vžiť do situácie študenta: Príde záverečná skúška a Vy dostanete na skúške algoritmus, ktorý ste nikdy pred tým nevideli. Jediná pomôcka je, že poznáte iba týchto 5 zložitostí: [mathjax]n, n\log n, n^{2}, n^{3}, 2^{n}[/mathjax].
Ako by ste hľadali jeho minimálnu, priemernú a maximálnu zložitosť. Skúste aspoň slovný postup bod po bode.

Ďakujem za odpoveď a ochotu.