完全二叉树时间复杂度

Question

如果有人想生成一棵完整的二叉树。这棵树有 h 层，其中 h 可以是任何正整数并作为算法的输入。它的复杂性是什么？为什么？

Answer 1

完全二叉树是除最后一层外所有层都充满节点的树，我们可以用上界来定义时间复杂度。

如果我们知道树的高度是h，那么树中最大可能的节点数是2^h - 1.

因此，时间复杂度=O(2^h - 1).

要在市场上销售你的算法，你需要严格的上限来证明你的算法比别人的好。

在确切知道树中有多少个节点后，可以为这个问题定义一个稍微严格的上限。假设有 N.

那么，时间复杂度=O(N)。