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!
Pocet porovnani pri trideni QuickSortem
- twoflower
- Supermatfyz(ák|ačka)
- Příspěvky: 445
- Registrován: 22. 9. 2004 21:07
- Typ studia: Informatika Ph.D.
- Kontaktovat uživatele:
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 obhajiljs píše:No me by se taky nejake DOBRE (smysluplne, pripadne i komentovane) poznamky hodilyChe 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á...
-
- 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:
Jo, je to skoro to stejny - u BST vybiras vrchol, co bude v korenu a u QuickSortu pivot...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
QuickSort trochu jinak
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.
Re: QuickSort trochu jinak
Přesunul se na http://ksp.mff.cuni.cz/viz/kucharky/trideniMJ 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.