IT rekvalifikácia. Seniorní programátori zarábajú až 6 000 €/mesiac a rekvalifikácia je prvým krokom. Zisti, ako na to!

Diskusia – Dolný odhad zložitosti problému triedenia

Späť

Upozorňujeme, že diskusie pod našimi online kurzami sú nemoderované a primárne slúžia na získavanie spätnej väzby pre budúce vylepšenie kurzov. Pre študentov našich rekvalifikačných kurzov ponúkame možnosť priameho kontaktu s lektormi a študijným referentom pre osobné konzultácie a podporu v rámci ich štúdia. Toto je exkluzívna služba, ktorá zaisťuje kvalitnú a cielenú pomoc v prípade akýchkoľvek otázok alebo projektov.

Komentáre
Avatar
tonislav.strnad
Člen
Avatar
tonislav.strnad:25.10.2012 12:26

ahoj, ja jsem trochu zmatenej
kdyz si za n dosadim 4. n! je mensi nez n/2 * n/2 (n/2krát) tak

4! není menší než 2*2 .
:(

 
Odpovedať
25.10.2012 12:26
Avatar
matesax
Tvůrce
Avatar
Odpovedá na tonislav.strnad
matesax:25.10.2012 12:50

Je to nekonečná řada...

 
Odpovedať
25.10.2012 12:50
Avatar
Kit
Tvůrce
Avatar
Kit:25.10.2012 18:25

Ještě bys mohl napsat článek o odhad složitosti problému řazení, protože třídění se dělá jen výjimečně, ale řazení se dělá velmi často.

Odpovedať
25.10.2012 18:25
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
trantanh
Člen
Avatar
trantanh:3.5.2015 20:44

nemáš náhodou ten obrázek špatně popsány?

 
Odpovedať
3.5.2015 20:44
Avatar
mochhito
Člen
Avatar
mochhito:16.6.2015 13:36

Ahoj, tu nerovnost mas naopak.
(vid obrazok)

 
Odpovedať
16.6.2015 13:36
Avatar
Patrik Pastor
Člen
Avatar
Patrik Pastor:21.4.2019 10:00

proc jsi na konci toho jmenovatele vynasobil *2? ted

n*log(n)/2 - 1, jsi udelal n*log(n) /4

dik, za odpoved

 
Odpovedať
21.4.2019 10:00
Avatar
Patrik Pastor
Člen
Avatar
Odpovedá na matesax
Patrik Pastor:21.4.2019 20:43

jak nekonecna rada, neni tam snad n/2 prvku? to mi prijde jako konecne

 
Odpovedať
21.4.2019 20:43
Avatar
Patrik Pastor
Člen
Avatar
Patrik Pastor:21.4.2019 20:46

"log 2 je 1, tu zanedbám a zvýším jmenovatel)." 1 zanedbam kvuli limite, ktera jde do nekonecna? (pokud je tedy cely vypocet myslen pro nekonecne rady, pokud ano, bylo by dobre to v clanku uvest), a stale nechapu proc se jmenovatel vynasobil dvemi.

Editované 21.4.2019 20:47
 
Odpovedať
21.4.2019 20:46
Avatar
Martin Dráb
Tvůrce
Avatar
Odpovedá na Patrik Pastor
Martin Dráb:22.4.2019 10:35

ahoj, ja jsem trochu zmatenej

Článek mluví o odhadu asymtrotické časové složitosti, což zjednodušeně znamená, že se bavíme o velkých hodnotách n (určitě větších než 4) a konstanty nás příliš nezajímají.

jak nekonecna rada, neni tam snad n/2 prvku? to mi prijde jako konecne

To je takové to potenciální nekonečno. n sice není nekonečné, ale může být libovolně velké. Pro skutečně nekonečný počet prvků se nemá smysl problémem řazení příliš zabývat, neb to v konečném čase zřejmě nezvládneme :-).

Já bych pro nahlédnutí logaritmu z n! použil spíše Stirlingovu formuli, protože není třeba provádět "šaškování" s nerovnicemi a jejich zdánlivě zvláštními úpravami (pokud dokážeme přijmout, že ta formule platí).
https://en.wikipedia.org/…pproximation

Editované 22.4.2019 10:36
Odpovedať
22.4.2019 10:35
2 + 2 = 5 for extremely large values of 2
Avatar
Jiří Šála
Člen
Avatar
Jiří Šála:15. januára 12:21

Článek v pohodě. Jen menší matematické chyby. Jen, že ty odhady n! v článku mají špatné nerovnosti!! Mají být opačně. Tam je chyba.
Jinak myšlenka se zachová. Totiž to h ještě zmenšujeme pod n! a ukazujeme, že i přes to musí být minimálně asymptoticky rádu O(n*log2(n)) a samozřejmě platí i pro dekadický logaritmus, protože se liší jen vynásobenou konstantou log2, kterou v sobě zahrnuj ten symbol O. Je to jen detail, ale čtou to lidi, tak na to upozorňuji.
Jinak jsem spokojen. Jiří Šála

 
Odpovedať
15. januára 12:21
Robíme čo je v našich silách, aby bola tunajšia diskusia čo najkvalitnejšia. Preto do nej tiež môžu prispievať len registrovaní členovia. Pre zapojenie sa do diskusie sa zaloguj. Ak ešte nemáš účet, zaregistruj sa, je to zadarmo.

Zatiaľ nikto nevložil komentár - buď prvý!