NOVINKA: Získej 40 hodin praktických dovedností s AI – ZDARMA ke každému akreditovanému kurzu!
S účinností od 26. 3. jsme aktualizovali Zásady zpracování osobních údajů – doplnili jsme informace o monitorování telefonických hovorů se zájemci o studium. Ostatní části zůstávají beze změn.

Diskuze – Lekce 7 - Dolní odhad složitosti problému třídění

Zpět

Upozorňujeme, že diskuze pod našimi online kurzy jsou nemoderované a primárně slouží k získávání zpětné vazby pro budoucí vylepšení kurzů. Pro studenty našich rekvalifikačních kurzů nabízíme možnost přímého kontaktu s lektory a studijním referentem pro osobní konzultace a podporu v rámci jejich studia. Toto je exkluzivní služba, která zajišťuje kvalitní a cílenou pomoc v případě jakýchkoli dotazů nebo projektů.

Komentáře
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 .
:(

 
Odpovědět
25.10.2012 12:26
Avatar
matesax
Tvůrce
Avatar
Odpovídá na tonislav.strnad
matesax:25.10.2012 12:50

Je to nekonečná řada...

 
Odpovědět
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.

Odpovědět
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?

 
Odpovědět
3.5.2015 20:44
Avatar
mochhito
Člen
Avatar
mochhito:16.6.2015 13:36

Ahoj, tu nerovnost mas naopak.
(vid obrazok)

 
Odpovědět
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

 
Odpovědět
21.4.2019 10:00
Avatar
Patrik Pastor
Člen
Avatar
Odpovídá na matesax
Patrik Pastor:21.4.2019 20:43

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

 
Odpovědět
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.

Editováno 21.4.2019 20:47
 
Odpovědět
21.4.2019 20:46
Avatar
Martin Dráb
Tvůrce
Avatar
Odpovídá 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

Editováno 22.4.2019 10:36
Odpovědět
22.4.2019 10:35
2 + 2 = 5 for extremely large values of 2
Avatar
Jiří Šála
Člen
Avatar
Jiří Šála:15.1.2024 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

 
Odpovědět
15.1.2024 12:21
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 10 zpráv z 10.