2. sada domácich úloh

Moderátor: FeroG

<<

FeroG

Príspevky: 1290

Registrovaný: Uto Máj 29, 2007 11:25 am

Poslať Štv Mar 18, 2010 12:48 pm

johny píše:Dokonca Theta(n log n), je to riešenie rekurencie T(n) = 2T(n/2) + n

To asi nie je tak celkom pravda, kedze nie je garantovane, ze uzlov v lavom a pravom podstrome bude priblizne rovnako. Staci zobrat degenerovany strom s linearnou hlbkou - tam to pojde k Theta(n^2). T.j. nasadi sa podobny argument, ako pri dokaze toho, ze QuickSort moze byt v najhorsom pripade az kvadraticky.

//EDIT: Jano ma predbehol a upravil svoj prispevok, takze moj komentar uz je neaktualny...

Pamat aspon O(h) bude treba, aby sa vedelo v strome navigovat (ulozenie navigacnej cesty). Usetrit pamat ide iba pri uplnych binarnych stromoch pri vhodnej reprezentacii.
<<

johny

Príspevky: 132

Registrovaný: Pia Feb 22, 2008 6:37 pm

Bydlisko: Košice

Poslať Štv Mar 18, 2010 12:52 pm

FeroG píše://EDIT: Jano ma predbehol a upravil svoj prispevok, takze moj komentar uz je neaktualny...


:D

Ale zase som doplnil pekné intuitívne vysvetlenie ;)
E-mail/Jabber: jan[zavináč]jergus.eu
<<

FeroG

Príspevky: 1290

Registrovaný: Uto Máj 29, 2007 11:25 am

Poslať Štv Mar 18, 2010 7:15 pm

johny píše:Alebo intuitívne: Na hodnotu každého z n vrcholov sa pozrieme práve raz pri spracúvaní každého z jeho predkov, ktorých je O(log n).

Ale zase som doplnil pekné intuitívne vysvetlenie ;)

Dokonca viac. Z tvojho intuitivneho argumentu vyplyva, ze casova zlozitost implementacie podla definicie je O(n.h), kde n je pocet uzlov stromu a h je vyska stromu. To dava O(n.log(n)) pre vyvazene stromy a O(n^2) pre degenerovane stromy.
<<

kvietok

Príspevky: 7

Registrovaný: Ned Okt 18, 2009 11:29 am

Poslať Sob Mar 20, 2010 2:52 pm

no tak mala otazka.. vadi ak metoda pocet listov bude v public int?
<<

FeroG

Príspevky: 1290

Registrovaný: Uto Máj 29, 2007 11:25 am

Poslať Sob Mar 20, 2010 5:58 pm

kvietok píše:no tak mala otazka.. vadi ak metoda pocet listov bude v public int?

Nielen, ze nevadi, ale to tak aj ma byt. V zadani som spravil chybu v hlavicke metody. Dakujem za upozornenie.
<<

mirak

Príspevky: 119

Registrovaný: Štv Okt 01, 2009 9:24 pm

Bydlisko: Kosicky Invader

Poslať Ned Mar 21, 2010 3:31 am

pytaj si bonusovy bod! :lol: (doc. krajci za najdenie chyby v skriptach dava tiez body) 8)
<<

zt

Príspevky: 199

Registrovaný: Uto Feb 26, 2008 8:26 pm

Poslať Str Mar 24, 2010 10:08 pm

v metode public int pocetListov() nema byt nejaky vstupny parameter este?
<<

FeroG

Príspevky: 1290

Registrovaný: Uto Máj 29, 2007 11:25 am

Poslať Str Mar 24, 2010 10:35 pm

Nie, metoda pocetListov nema ziadne vstupne parametre. Jednoducho uzla sa pytame kolko listov ma strom, ktoreho on je korenom.
<<

FeroG

Príspevky: 1290

Registrovaný: Uto Máj 29, 2007 11:25 am

Poslať Str Mar 24, 2010 10:42 pm

Komentar k ulohe removeAll. Aby ste sa vyhli sklamaniu z neakceptovania riesenia, pred odoslanim vyskusajte tieto zoznamy a odstranenie hodnoty 3:
[] - prazdny zoznam
[3]
[3, 3, 3, 3, 3]
[3, 3, 3, 3, 5, 5, 5, 3, 3, 3, 6, 6, 6, 3, 3, 3]
<<

zt

Príspevky: 199

Registrovaný: Uto Feb 26, 2008 8:26 pm

Poslať Str Mar 24, 2010 11:06 pm

ked ma strom jeden uzol ktory je zaroven jeho korenom tak ma jeden list ci to za nepocita este ako list?
<<

FeroG

Príspevky: 1290

Registrovaný: Uto Máj 29, 2007 11:25 am

Poslať Str Mar 24, 2010 11:11 pm

zt píše:ked ma strom jeden uzol ktory je zaroven jeho korenom tak ma jeden list ci to za nepocita este ako list?

Ano, aj koren moze byt listom.
Predchádzajúci

Späť na PAZ1b

Kto je on-line

Užívatelia prezerajúci fórum: Žiadny registrovaný užívateľ nie je prítomný a 2 hostia

cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by ST Software.
Slovenský preklad.