Złożoność dla maxheight funkcji w binarnym drzewie

Question

Funkcja:

MAX-HEIGHT(node) 
    if(node == NIL) 
     return -1; 
    else 
    return max(MAX-HEIGHT(node.leftChild), MAX-HEIGHT(node.rightChild)) + 1; 

Załóżmy, że mamy N węzłów i wywołać funkcję z MAX-HEIGHT(root).

myślę, że złożoność tej funkcji jest O (N), ponieważ musimy odwiedzić każdy węzeł. Jednak nie jestem pewien i nie mogę tego udowodnić rygorystycznie. Proszę podać mi dobre wyjaśnienie, dlaczego jest to O (N), jeśli jest to O (N), i dlaczego nie, jeśli nie jest O (N).

Co to jest złożoność?

Dziękuję.

Answer 1

W przypadku średniej dla zrównoważonej drzewa binarnego

T(n) = 2T(n/2) + Θ(1); 

Każde wywołanie rekurencyjne daje dwa problemy połowę mniejszy. Zgodnie z twierdzeniem mistrza oceniłoby to T (n) = Θ (n)

W najgorszym przypadku, gdy każdy węzeł ma tylko jedno dziecko.

T(n) = T(n-1) + Θ(1) 

rozpoznawaną T (n) = Θ (n)

Answer 2

pytania należy zadać to:

• Co N reprezentowania w moim struktury danych (drzewo binarne)
• Ile N trzeba przejść, zanim będę mógł określić wysokość mojej struktury.

Tutaj N oznacza liczbę węzłów w twoim drzewie i musisz przejść przez wszystkie z nich przed zwróceniem wysokości.

Z tego powodu Twój algorytm jest w O (N)