Pocet porovnani pri trideni QuickSortem

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:
BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí
Přehled tématu
   

Rozšířit náhled Přehled tématu: Pocet porovnani pri trideni QuickSortem

Re: QuickSort trochu jinak

od Návštěvník » 4. 1. 2013 07:49

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

QuickSort trochu jinak

od MJ » 13. 7. 2005 22:43

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.

od Eubie » 6. 7. 2005 09:46

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

od krystof » 3. 7. 2005 23:45

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...

od twoflower » 26. 6. 2005 08:55

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 :)

od js » 26. 6. 2005 05:26

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:

od Che » 25. 6. 2005 19:33

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á... :?

Pocet porovnani pri trideni QuickSortem

od twoflower » 25. 6. 2005 19:01

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!

Nahoru