老师，关于线段树的问题
来源：9-6 线段树中的更新操作
相信光变成光
2018-12-25
老师，你在更新操作这一视频中的10分33秒左右说，构建线段树的复杂度是O(4n)
因为构建过程使用的是递归，难道不是O（logn）吗？？？还是你说的是空间复杂度。
写回答
1回答
-
liuyubobobo
2018-12-25
线段树一共有O(4n)个节点，在建立的过程中，每个节点被遍历了一次，所以时间复杂度是O(4n) = O(n)：）
其实，这个时间复杂度，和树的遍历的时间复杂度是一样的。回忆一下，便利一棵BST的时间复杂度是O(n)的，因为每个节点访问一次。
不是一有树，时间复杂度就是O(logn)的，O(logn)是树的高度。只有在我们的算法只从根走到一个叶子，这个算法才是O(logn)的。对于遍历过程，从根节点，到每一个叶子，都要走到：）
继续加油！
20
相似问题