问二叉树数组列表表示
EN

Stack Overflow用户

提问于 2012-10-29 12:23:29

回答 1查看 2.6K关注 0票数 0

我一直在研究二叉树和数组列表表示。我正在努力理解最坏情况下的空间复杂度是O(2^n)。具体地说，书中指出，空间使用量是O (N ) (N=数组大小)，在最坏的情况下是O(2^n)。我认为在最坏的情况下应该是2n，因为每个节点都有两个子节点(索引)，而不是O(2^n)，其中n= no。元素的集合。

例如，如果我有一个包含7个节点的二叉树，那么空间应该是2n = 14而不是2^n = 128。

发布于 2012-10-29 12:37:35

二叉树的最坏情况空间复杂度是O(n) (在您的问题中不是O(2^n) )，但是如果二叉树几乎是一棵完整的二叉树，那么使用数组来表示二叉树可以节省指针空间。

请参阅http://en.wikipedia.org/wiki/Binary_tree#Arrays

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/13115830

复制

相似问题

问二叉树数组列表表示EN