W jaki sposób można określić wysokość drzewa rekursji, zbudowanego podczas rozwiązywania problemów z czasem cyklu? Czym różni się od określenia wysokości zwykłego drzewa?Jak określić wysokość drzewa rekursji ze związku rekurencyjnego?
alt text http://homepages.ius.edu/rwisman/C455/html/notes/Chapter4/ch4-9.gif
edit: przepraszam, chciałem dodać, jak uzyskać wysokość drzewa rekursji z relacji nawrotom.
Wysokość drzewa rekursji zależy od algorytmu rekurencyjnego, o którym mowa. Nie wszystkie algorytmy dzielą i podbijają umundurowane drzewa wysokości, tak jak nie wszystkie struktury drzew mają jednakowe wysokości. Jeśli nie możesz określić maksymalnej możliwej wysokości algorytmu lub jeśli musisz obliczyć rzeczywistą wysokość drzewa w czasie wykonywania, możesz użyć zmiennej globalnej do funkcji rekursywnej, zwiększyć ją po wejściu do funkcji i zmniejszyć po wyjściu funkcji. Ta zmienna wskaże aktualny poziom procedury rekursywnej. W razie potrzeby można utrzymać maksymalną wartość tej zmiennej w drugiej zmiennej.
Po pierwsze, jeśli jest to zadanie domowe, proszę oznaczyć je jako takie. Obrazy, które łączysz z sugestią, że jesteś w CS 455, z profesorem Wismanem. :)
Główna wskazówka, jaką dam, to: Wysokość drzewa jest oczywiście określona przez kiedy dojdziesz do "liści". Liście drzewa modelujące relację nawrotu funkcji są przypadkiem podstawowym. W związku z tym chciałbym zobaczyć, jak "szybko" N może zmniejszyć się do przypadku podstawowego.
To nie jest praca domowa:) Osobiste studium. Obraz, z którym się łączyłem, był najbardziej trafny w przypadku obrazów google. Powinienem to wcześniej wyjaśnić, przepraszam! – Chris
Przepraszamy, dodaliśmy komentarz za wcześnie. Twoja odpowiedź na pewno ma sens. Jednak zazwyczaj nie można podążać za liśćmi w dół. Tworzenie pierwszych kilku gałęzi jest banalne. Stamtąd to mnie trochę zdezorientowało :) – Chris
Jeśli rekurencja ma postać T (n) = aT (n/b) + f (n), wówczas głębokość drzewa to podstawa log b n.
Na przykład 2T (n/2) + n powtórzenia będzie mieć drzewo o głębokości lg (n) (podstawa logu 2 n).
Strzelanie z mojego tyłka tutaj, ale nie widzę różnicy. Dlaczego uważasz, że istnieje różnica? W skrócie, są to oba drzewa ... –
zobacz moją odpowiedź tutaj: http://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly/13093274#13093274 – 2cupsOfTech