Zk 21. 1. 2014

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: Zk 21. 1. 2014

Re: Zk 21. 1. 2014

od emu » 21. 1. 2014 19:28

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

Zk 21. 1. 2014

od MaM » 21. 1. 2014 17:29

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.

Nahoru