解释这个用于查找高度的 python TREE 算法的运行时间解释这个用于查找高度的

Question

下面我附上了一段代码。请你们告诉我下面的代码如何具有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)时间复杂度中是如何工作的。请帮助我学习这一点。

Answer 1

假设n代表树中的节点数，我们可以观察到以下情况：c in self.children(p)永远不会产生相同的c两次：除根之外的所有节点在某个时刻都将是该c，并且仅一次。所以这段代码代表每个节点的恒定时间复杂度。此外，_height2将为所有节点调用一次。对于根，这是初始调用，对于所有其他节点，这是递归调用。所有其他代码（除了对子节点的迭代和递归调用之外）表示每个节点的恒定时间复杂度。所以我们的时间复杂度是O(n) 。