为什么二叉树遍历（如前序）的时间复杂度不是指数级的？

Question

为什么二叉树遍历（如前序）的时间复杂度不是指数级的？例如，在斐波那契数列的常见实现中，它是指数级的，因为对于每个实例，您都会调用斐波那契函数两次。那么，为什么前序遍历是 O(n)（递归函数也被调用两次） [我知道它是 O(n)，因为遍历每个节点，所以请不要回答为什么它是 O(n)。与斐波那契递归实现比较的答案，因为我想看看区别。

Answer 1

有两种查看方式：

对于每个节点，您正好进行了两次递归调用。这已经告诉您它是每个附加节点的常数因子，无论该节点位于树中的哪个位置。

但以防万一这对你来说还不够，还有其他观点：

在每次递归调用中，子问题减半。因此，您将调用量加倍，但要完成的工作量减半。

这两种情况都不同于“有缺陷的斐波那契实现”，因为您永远不会多次访问一个节点。在斐波那契示例中，您一遍又一遍地做同样的工作。

Answer 2

我假设您指的是递归斐波那契算法，它以数字作为输入，returns 来自斐波那契数列的第 ^th 数字：

def fibonacci(number):
  if number < 2:
    return number
  else:
    return fibonacci(number - 1) + fibonacci(number - 2)

如果我们将 number 的每个不同值（用于调用此函数）视为一个“节点”，那么请注意与二叉树遍历问题的重要区别：

此 Fibonacci 算法将访问同一节点多次，并且随着对已访问“节点”进行递归调用，情况变得更糟。递归树不是真正的树，而是有向无环图。这是调用 Fibonacci(5):

时的递归树

所以我们看到Fibonacci(3)被计算了两次，每次都完成更深层次递归的全部工作。所以 Fibonacci(2) 和 Fibonacci(0) 各被调用 3 次， Fibonacci(1) 被调用 5 次。总共有 15 次“访问”，包括重复。

递归树遍历算法不会发生这种情况，递归树实际上是一棵树（相当于被遍历的树）。

这解释了时间复杂度的差异。

这也解释了为什么可以通过避免重复的“节点访问”来改进这种朴素的斐波那契算法，使其也变成 O(n)。

为什么二叉树遍历（如前序）的时间复杂度不是指数级的？

Why is time complexity of binary tree traversal (like preorder) not exponential?

algorithm

tree