Fórum studentů MFF UK

Myslím, že ta halda v lin. čase spočívá v tom, že se staví odspoda (takže u heapsortu odzadu)

Him píše:HonzaK: jak se dela to vytvareni haldy v lin. case? jen se pridavaji prvky a nic se nedela? Dik

Dela se to, jak to Holan nazval, "ucetnickym trikem":
Vyjde se z toho, ze pri reprezentaci haldy temer uplnym bin. stromem se velka cast vrochlu nachazi bud v posledni hladine (tj. jsou to listy), nebo predposledni hladine - celkem to vzhledem k exponencialnimu rustu poctu vrcholu vzhledem k hladinam dela n/2 vsech vrcholu, ktere se uz vemou, ze jsou na svem miste, tj. cas na jejich umisteni je 0 (pri reprezentaci polem to odpovida druhe polovine pole). Dale se vezmou vrcholy, ktere tvori zbytek predposledni hladiny a cast predpredposledni - tech je n/4 a na vlozeni kazdeho z nich potrebujeme max 1 prohozeni (s nejakym vrcholem, ktery uz v hlade je). Pak se vezme dalsich n/8 vrcholu (na umisteni kazdeho z nich potrebujeme max 2 prohozeni), pak n/16 atd.

Tedy celkem je potrebny cas: 0*n/2 + 1*n/4 + 2*n/8 + ... coz je O(n)

Takze tak nejak...

Kdybyste někdo náhodou chtěli brát moc vážně to řešení, co jsem tam napsal, tak to neděleljte, není dobře ... Ale kdyby se to kapánek předělalo, tak to bude fungovat dobře. A mohlo by to mít ještě mnohem menší složitost, jelikož je mnoho tahů, kdy se vlastně nic neděje.

Lidi, dá se na téhle zkoušce vyletět?

U Topfera to asi možný je... když zvoráš ten algoritmus, tak budeš muset bojovat o 3 (pokud nepůjdeš rovnou)... ale to jsem tak slyšel... já byl u Holana

Mohli byste někdo, kdo už má tuhle zkoušku za sebou napsat z čeho jste se učili, atp? Hlavně moc nechápu, jak moc podrobně to musí být u té písemné části rozebrané. Jestli stačí napsat např. teď si vygeneruju stavový prostor, a prohledávám do hloubky, nebo tam bazírujou na detailech?

DÍK

No musí bejt jasný, jak bys to udělal. Aby z toho bylo vidět, že si uvědomuješ, jak konkrétně by se to napsalo, jak přesně by vypadaly datové struktury, aby z toho byla vidět složitost... Určitě nebazírujou na detailech, musí tam bejt to podstatný, to důležitý. Pokud nějakou důležitou věc ohledně řešení budeš vědět akle nenaúpíšeš ji tam, tak to není dobré. Já osobně jsem popsal asi 6 těch velkejch stránek a musel jsem si během toho ořezávat tužku, ale myslím, že jsem to psal zbytečně moc podrobně. Každopádně káš 2 hpdiny času, to toho člověk stihne napsat dost, mě by byla stačila hodka a půl.
Na písemku jsem se neučil. Na ústní jsem se učil z poznámek a ze slajdů co má topfer na stránkách, a co se týče těch stromů a takovejch těch datovejch struktur, tak na to jsem kouk v Algovision.

rozhodne nebazirujou na detailech ale musi bejt videt ze vis jak bys to udelal.
jiank z tech peti tematovejch okruhu co tam mame napsat (postrehy, algoritmus, ds, atd atd) jsem mel jeden a pul a stejne, jelikoz jsem tam mel vsechno dulezity, tak to bylo za jedna.

Máte někdo tušení, jak aspoň začít s řešením tohohle příkládku? Nějak vůbec nevím, kde začít a dle čeho navyšovat. Díky
Zadání: http://forum.matfyz.info/viewtopic.php?t=1885