Объясните время выполнения этого алгоритма дерева Python для нахождения высот

#python #python-3.x #data-structures #tree

#python #python-3.x #структуры данных #дерево

Вопрос:

Здесь ниже я прикрепил блок кода. Ребята, пожалуйста, расскажите, как следующий код имеет время выполнения O (n).

 def _height2(self, p):
     if self.is_leaf(p):
          return 0
     else:
          return 1   max(self._height2(c) for c in self.children(p))

Я не могу понять, как это работает при O (n) временной сложности.
Пожалуйста, помогите мне изучить это.

1. это было бы порядка n, если бы была задействована некоторая запоминание.

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

Ответ №1:

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

c in self.children(p) никогда не будет выдавать один и тот же c дважды: все узлы, кроме корневого, в какой-то момент будут такими c, и только один раз. И поэтому этот код представляет постоянную временную сложность для каждого узла. Более того, _height2 будет вызываться для всех узлов ровно один раз. Для корня это начальный вызов, а для всех остальных узлов это рекурсивный вызов.

Весь остальной код (кроме итерации по дочерним элементам и рекурсивного вызова) представляет собой постоянную временную сложность для каждого узла.

Итак, у нас есть O (n) временная сложность.