线段树空间复杂度问题
来源：9-1 什么是线段树
Grant_Lian
2018-11-11
老师，我看您的线段树推倒空间复杂度的index转换感觉有点疑问，我是这么想的，线段树 0层->1个节点，2层->2个节点，。。。。h-1层：2^（h-1） 个节点，根据等比数列求和，要用等比数列我们层数从1开始，所以总共2 ^ (h+1) - 1个节点，约等于2 ^ (h + 1), 如果我们去掉最后一层的话前面的层加起来总共约等于2 ^ h, 最后一层2 ^ (h - 1)个节点，二倍关系可以看成一样，最后2n，但是怎么能知道2 ^ h 和2 ^ (h - 1)约等于 n呢？谢谢老师。
写回答
1回答
-
赞！你的分析没有错。不过在复杂度分析中，O(2n) 是等于 O(n) 的：）
大O是渐进复杂度，一切系数，常熟，低阶项，在大O表示法中，都没有意义：）
继续加油！：）
252018-11-11
相似问题
老师，关于线段树的问题
回答 1
红黑树的高度问题
回答 1