Pocet porovnani pri trideni QuickSortem

Uživatelský avatar
twoflower
Supermatfyz(ák|ačka)
Příspěvky: 445
Registrován: 22. 9. 2004 21:07
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Pocet porovnani pri trideni QuickSortem

Příspěvek od twoflower »

Zdravim,

nehodil by sem nekdo prosim oskenovane zapisky z prednasky k tomuhle tematu? V sesite mam jen poznamenano: "Tak tohle nechapu", z cehoz se moc dobre neda ucit...Diky moc!
Uživatelský avatar
Che
Donátor
Donátor
Příspěvky: 166
Registrován: 2. 6. 2005 12:29
Typ studia: Informatika Mgr.
Bydliště: EU
Kontaktovat uživatele:

Příspěvek od Che »

No, takový trochu "jiný" důkaz průměrného počtu porovnání u quicksortu je v Kapitolách DM na str. 287.

Ale nějaké dobré oskenované zápisky by se mi taky hodily a nejen u quicksortu... No, zkouška bude asi zajímavá... :?
shoot that shit
js
Site Admin
Příspěvky: 144
Registrován: 22. 9. 2004 06:06
Typ studia: Fyzika Ph.D.
Bydliště: Praha

Příspěvek od js »

Che píše:...
Ale nějaké dobré oskenované zápisky by se mi taky hodily a nejen u quicksortu... No, zkouška bude asi zajímavá... :?
No me by se taky nejake DOBRE (smysluplne, pripadne i komentovane) poznamky hodily :cry:
JS
Uživatelský avatar
twoflower
Supermatfyz(ák|ačka)
Příspěvky: 445
Registrován: 22. 9. 2004 21:07
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Příspěvek od twoflower »

js píše:
Che píše:...
Ale nějaké dobré oskenované zápisky by se mi taky hodily a nejen u quicksortu... No, zkouška bude asi zajímavá... :?
No me by se taky nejake DOBRE (smysluplne, pripadne i komentovane) poznamky hodily :cry:
Asi tak..nemohl by sem nekdo aspon postnout ideu toho dukazu? Neni to podobny jako prumerneha hloubka prumerneho BST? To uz bych pak vedel :) Jinak na ted dukaz v Kapitolach z DM jsem koukal, opravdu netradicni pristup, rekl bych, ale nevim jestli bych to u Kucery obhajil :)
krystof
Matfyz(ák|ačka) level III
Příspěvky: 186
Registrován: 18. 1. 2005 15:15
Typ studia: Informatika Mgr.
Bydliště: Brno / 17. Listopad
Kontaktovat uživatele:

Příspěvek od krystof »

twoflower píše:Asi tak..nemohl by sem nekdo aspon postnout ideu toho dukazu? Neni to podobny jako prumerneha hloubka prumerneho BST? To uz bych pak vedel :) Jinak na ted dukaz v Kapitolach z DM jsem koukal, opravdu netradicni pristup, rekl bych, ale nevim jestli bych to u Kucery obhajil :)
Jo, je to skoro to stejny - u BST vybiras vrchol, co bude v korenu a u QuickSortu pivot...
Eubie

Příspěvek od Eubie »

Mozna uz je pozde, nicmene na matfyz.mysteria.cz je k nalezeni dokument Algoritmy a datove struktury a v nem tento dukaz je.
MJ

QuickSort trochu jinak

Příspěvek od MJ »

Trochu neortodoxní, ale doufám, že pěkný a hlavně jednoduchý důkaz složitosti QS je k nalezení na http://ksp.mff.cuni.cz/temp/tasks1.ps na straně 9. (Časem se přesune na titulní stránku webu.) Zn.: Bez záruky.
Návštěvník

Re: QuickSort trochu jinak

Příspěvek od Návštěvník »

MJ píše:Trochu neortodoxní, ale doufám, že pěkný a hlavně jednoduchý důkaz složitosti QS je k nalezení na http://ksp.mff.cuni.cz/temp/tasks1.ps na straně 9. (Časem se přesune na titulní stránku webu.) Zn.: Bez záruky.
Přesunul se na http://ksp.mff.cuni.cz/viz/kucharky/trideni
Odpovědět

Zpět na „2004“