performance - 时间复杂度，二叉（搜索）树

Question

假设我有一个完整的二叉树，直到一定深度d。遍历（前序遍历）这棵树的时间复杂度是多少。

我很困惑，因为我知道树中的节点数量是 2^d，所以时间复杂度是BigO(2^d)？因为这棵树呈指数增长。

但是，在互联网上的研究中，每个人都说遍历是BigO(n)其中 n 是元素的数量（2^d在这种情况下是），而不是BigO(2^d)，我错过了什么？

谢谢

score 3 · Accepted Answer

n 定义为节点数。

2^d 只是该深度的每个可能节点都已满时的节点数

IE。

     o
   /   \
  o     o
 / \   
o   o

当 2^d 为 8 时只有 5 个节点

完整的二叉树除了最后一行之外的所有节点都被填充，并且所有节点都填充到左侧。你可以在维基百科上找到定义

score 0 · Accepted Answer

即使您可以将时间复杂度表示为 O(2^d)，这也没什么用，因为您无法将其与任何其他集合的时间复杂度进行比较。

另一方面，将时间复杂度表示为 O(n) 非常有用。它准确地告诉您当您增加项目数量时集合如何反应，而无需确切知道集合是如何实现的，并且您可以将其与其他集合的时间复杂度进行比较。

2 回答 2