Stránka 1 z 1

Zk 21. 1. 2014

Napsal: 21. 1. 2014 17:29
od MaM
Dostal jsem fibonaciho haldy. Slovne jsem presne popsal jak probihaji operace (insert, min atd). Napsal slozitosti a rekl, jaky jsou amortizovany slozitosti. Nemel jsem to uplne tip top jako v knizce, ale vse hned proslo. Pak jsem se snazil dokazat amortizovanou slozitost (dukaz pres fibonaciho cisla). Tam jsem se trochu zasekl, tak pak jsem jen dopsal myslenku. Tzn i-ty strom ma alespon Fi+2 vrcholu a fib cisla rostou exponencialne, tzn staci log stromu (zkracene receno). Vse stacilo na 1.

Takze je dulezite znat princip a vysvetlit ho, netreba to uplne exaktne spocitat.
Na 3 by urcite v pohode stacilo jen popsani operaci.

Re: Zk 21. 1. 2014

Napsal: 21. 1. 2014 19:28
od emu
Já jsem dostal A-sort, tak jsem se pozvolna rozpomenul na fungování ab-stromů a ve výsledku snad popsal algoritmus tak, jako byl na přednášce. Včetně složitosti, tu jsem si z části pamatoval a odvodit se dá docela snadno. Koubek se zeptal na pár podrobností, protože jsem řešení psal hodně random-access, a dal mi jedničku.

Teď mi dochází, že vlastně ani nemám ponětí, proč algoritmus čte posloupnost odzadu: popředu by podle mě fungoval taky.

Úspěšnost asi hodně záleží na otázce. Spolužák, co dneska přišel pozdě a neomluvil se, dostal perfektní hashování a radši šel rovnou zas domů.