线段树空间复杂度问题

Question

老师，我看您的线段树推倒空间复杂度的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呢？谢谢老师。

Answer 1

liuyubobobo 2018-11-11 02:11:43

赞！你的分析没有错。不过在复杂度分析中，O(2n) 是等于 O(n) 的：）

大O是渐进复杂度，一切系数，常熟，低阶项，在大O表示法中，都没有意义：）

继续加油！：）

• 提问者 Grant_Lian #1

  谢谢老师，我就是疑问这个h怎么和数组长度n对应上的，比如去掉最后一层，前面总共2 ^ h, 这个2  ^ h为什么和前面数组的长度n可以大致相等呢？谢谢老师的讲解

• liuyubobobo 回复 提问者 Grant_Lian #2

  就是你计算的等比数列求和公式啊：）实际画一个满二叉树试试看？最后一层的节点数等于前面所有层节点数 + 1：）

• 提问者 Grant_Lian #3

  非常感谢！

点开查看后面2条评论