Какова будет временная сложность оператора if?

Question

Ниже у меня есть алгоритм, который предназначен для возврата целочисленного значения, представляющего высоту двоичного дерева, и меня попросили выяснить, какова будет временная сложность его, вот код:

struct Node {
     int data;
     struct Node *left;
     struct Node *right; }

 int FindHeight(struct Node *root) {
     if (root == NULL)
           return -1;
     return max(FindHeight(root->1eft),FindHeight(root->right)) +1; 
}

Я прав, думая, что это будет 0 (1)?

Заранее большое спасибо.

Answer 1

Это не просто if -общение. Это max с рекурсивным вызовом.

Для вашего кода рекурсия go через все узлы. Он проходит через каждый узел один раз, поэтому временная сложность линейна O(n).

Глубина рекурсии может варьироваться в зависимости от древовидной структуры. Если дерево вырождено, сложность памяти O(n). В случае сбалансированного дерева сложность памяти составляет O(ln(n)).