我可以看到，当在 a 中查找值时，如何BST每次将节点与我们要查找的值进行比较时，我们都会留下一半的树。
但是我不明白为什么时间复杂度是O(log(n))。所以，我的问题是：
如果我们有一个包含 N 个元素的树，为什么查找树并检查特定值是否存在的时间复杂度是 O(log(n))，我们如何得到它？
你的问题似乎得到了很好的回答here https://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly但就您的具体问题进行总结时，最好反向思考； “随着节点数量的增加，BST 求解时间会发生什么变化”？
本质上，在 BST 中，每次将节点数量增加一倍，您只会将求解步骤数增加一倍。为了扩展这一点，四倍的节点提供了两个额外的步骤。八倍的节点提供了三个额外的步骤。十六个节点提供了四个额外的步骤。等等。
这些对中第一个数字的以 2 为底的对数是这些对中的第二个数字。它是以 2 为底的对数，因为这是二分搜索（每一步将问题空间减半）。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
