Stránka 2 z 2

PoslaťNapísal: Štv Mar 18, 2010 12:48 pm
od FeroG
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.

PoslaťNapísal: Štv Mar 18, 2010 12:52 pm
od johny
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 ;)

PoslaťNapísal: Štv Mar 18, 2010 7:15 pm
od FeroG
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.

PoslaťNapísal: Sob Mar 20, 2010 2:52 pm
od kvietok
no tak mala otazka.. vadi ak metoda pocet listov bude v public int?

PoslaťNapísal: Sob Mar 20, 2010 5:58 pm
od FeroG
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.

PoslaťNapísal: Ned Mar 21, 2010 3:31 am
od mirak
pytaj si bonusovy bod! :lol: (doc. krajci za najdenie chyby v skriptach dava tiez body) 8)

PoslaťNapísal: Str Mar 24, 2010 10:08 pm
od zt
v metode public int pocetListov() nema byt nejaky vstupny parameter este?

PoslaťNapísal: Str Mar 24, 2010 10:35 pm
od FeroG
Nie, metoda pocetListov nema ziadne vstupne parametre. Jednoducho uzla sa pytame kolko listov ma strom, ktoreho on je korenom.

PoslaťNapísal: Str Mar 24, 2010 10:42 pm
od FeroG
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]

PoslaťNapísal: Str Mar 24, 2010 11:06 pm
od zt
ked ma strom jeden uzol ktory je zaroven jeho korenom tak ma jeden list ci to za nepocita este ako list?

PoslaťNapísal: Str Mar 24, 2010 11:11 pm
od FeroG
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.