哪个时间复杂度更高？
哪个时间复杂度更高？
提问于 2017-12-05 00:31:52
我必须选择哪种操作在AVL树上比BST有更好的最坏情况时间复杂度。我已经确定每个操作的时间复杂度是相同的，这取决于树.
AVL树最糟糕的时间复杂度是..。
Insert - O(log(n))
Remove - O(log(n))
Search - O(log(n))BST最坏的时间复杂度是..。
Insert - O(height)
Remove - O(height)
Search - O(height)那么，O(log(n))比O(高度)更复杂吗？
回答 3
Stack Overflow用户
回答已采纳
发布于 2017-12-05 00:43:50
BST中用于插入、删除和搜索的最坏的时间复杂度是O(n)，其中n是BST中的节点数。您可以通过将节点按如下顺序插入BST，从而触发这种最坏的情况: BST本质上是一个链接列表(例如，首先插入1，然后插入2，然后插入3，等等)。您最终将得到一个类似于1 -> 2 -> 3的BST .)。
O(log(n))比O(n)具有更好的时间复杂度。
Stack Overflow用户
发布于 2017-12-05 00:44:00
O(log(n))是O(height)的最佳案例场景。二叉树的高度可以是log(n)和n之间的任意整数，其中n表示节点数。
例如，如果您有一个BST，其中每个节点只有正确的子节点，则它与链接列表相同，因此对于所有三个操作都具有O(n)最坏的情况复杂性。
另一方面，AVL是self-balancing二叉搜索树，这意味着来自任何节点的每两个子树都具有相同的深度(高度)+常数。这意味着您在每一步大约将值减半，从而获得O(log(n))复杂性，这也是您的O(height)复杂性。
Stack Overflow用户
发布于 2017-12-05 00:53:16
AVL树基本上是高度平衡的BST。如果考虑完整的AVL树，则log (AVL树)> log (BST)。->，其中n是节点数。
而当你考虑O(高度)时，它在AVL和BST中都是一样的。
3.
\
5 (BST)身高=2，n=2
3
/ \
2 5
(AVL)身高= 2，n=3
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/47644235
复制相关文章
相似问题
腾讯云开发者
