老师，关于线段树的问题

Question

老师，你在更新操作这一视频中的10分33秒左右说，构建线段树的复杂度是O(4n)
因为构建过程使用的是递归，难道不是O（logn）吗？？？还是你说的是空间复杂度。

Answer 1

liuyubobobo 2018-12-25 18:34:59

线段树一共有O(4n)个节点，在建立的过程中，每个节点被遍历了一次，所以时间复杂度是O(4n) = O(n)：）

其实，这个时间复杂度，和树的遍历的时间复杂度是一样的。回忆一下，便利一棵BST的时间复杂度是O(n)的，因为每个节点访问一次。

不是一有树，时间复杂度就是O(logn)的，O(logn)是树的高度。只有在我们的算法只从根走到一个叶子，这个算法才是O(logn)的。对于遍历过程，从根节点，到每一个叶子，都要走到：）

继续加油！