od jkt » 23. 2. 2010 00:42
Ke quicksortu (jsem nyni po 8+ viteznych Plznich, proto prosim omluvte souvislost projevu) -- popsal jsem algoritmus slovne, uvedl problemy s volbou pivota (konstatoval jsem, ze "pro libovolneho pivota existuje posloupnost, kde alg. pobezi v
", coz se doc. Koubkovi nezamlouvalo -- pokud jsem to v tuto hodinu schopen dat dohromady, jde cca. o to, ze pro kazdy pevne zadratovany algoritmus volby pivota existuje nejaky vstup, pro ktery alg. bezi v
, zatimco pri nahodne volbe pivota je takovy cas nejhorsi pro vsechny vstupy), uvedl, ze nahodna volba chce cas, a ze se typicky bere median ze tri ci peti pevne danych prvku, konstatoval, ze pri zohledneni multiplikativni konstanty jde o nejrychlejsi znamy alg. pro trideni zalozeny na vzajemnem porovnavani prvku, uvedl aplikaci pri hledani k-teho nejmensiho prvku, konstatoval, ze casova slozitost je v nejhorsim pripade
a v ocekavanem O(n lon g ), aplikoval to na odhad potrebneho prostoru, popsal algoritmus tez formalne, zduvodnil slozitost v nejhorsim pripade ("pivot je nejvetsi/nejmensi prvek, tedy v kazdem kroku rekurze ubyde prave jeden clen posloupnosti"), lehce naznacil dukaz slozitosti v ocekvanem pripade, kde jsem pohnojil znaceni prvku -- dle Koubkovo skript se v prvnim, "peknem" dukaze hovori v pripade prvku
o i-tem prvku ve vystupni posloupnosti, a vubec jsem nemel rozhodovaci strom o prubehu algoritmu,... -- popsal jsem ale sumaci
...
-> zkratka nakonec se urodila krasna a zdrava dvojka, ktera mne coby tatovi udelala velikou radost
.
Ke quicksortu (jsem nyni po 8+ viteznych Plznich, proto prosim omluvte souvislost projevu) -- popsal jsem algoritmus slovne, uvedl problemy s volbou pivota (konstatoval jsem, ze "pro libovolneho pivota existuje posloupnost, kde alg. pobezi v [latex]$$O(n^2)$$[/latex]", coz se doc. Koubkovi nezamlouvalo -- pokud jsem to v tuto hodinu schopen dat dohromady, jde cca. o to, ze pro kazdy pevne zadratovany algoritmus volby pivota existuje nejaky vstup, pro ktery alg. bezi v [latex]$$O(n^2)$$[/latex], zatimco pri nahodne volbe pivota je takovy cas nejhorsi pro vsechny vstupy), uvedl, ze nahodna volba chce cas, a ze se typicky bere median ze tri ci peti pevne danych prvku, konstatoval, ze pri zohledneni multiplikativni konstanty jde o nejrychlejsi znamy alg. pro trideni zalozeny na vzajemnem porovnavani prvku, uvedl aplikaci pri hledani k-teho nejmensiho prvku, konstatoval, ze casova slozitost je v nejhorsim pripade [latex]$$O(n^2)$$[/latex] a v ocekavanem O(n lon g ), aplikoval to na odhad potrebneho prostoru, popsal algoritmus tez formalne, zduvodnil slozitost v nejhorsim pripade ("pivot je nejvetsi/nejmensi prvek, tedy v kazdem kroku rekurze ubyde prave jeden clen posloupnosti"), lehce naznacil dukaz slozitosti v ocekvanem pripade, kde jsem pohnojil znaceni prvku -- dle Koubkovo skript se v prvnim, "peknem" dukaze hovori v pripade prvku [latex]$$ x_i $$[/latex] o i-tem prvku ve vystupni posloupnosti, a vubec jsem nemel rozhodovaci strom o prubehu algoritmu,... -- popsal jsem ale sumaci [latex]$$\sum_{i,j} X_{i j}$$[/latex]...
-> zkratka nakonec se urodila krasna a zdrava dvojka, ktera mne coby tatovi udelala velikou radost :).