为什么在二叉搜索树中查找为O(log(n))? [英] Why lookup in a Binary Search Tree is O(log(n))?

问题描述

我可以看到，在 BST 中查找值时，每次将节点与所需值进行比较时，我们都会留下一半的树.

I can see how, when looking up a value in a BST we leave half the tree everytime we compare a node with the value we are looking for.

但是我看不出为什么时间复杂度是O(log(n)).所以，我的问题是:

However I fail to see why the time complexity is O(log(n)). So, my question is:

如果我们有一棵由N个元素组成的树，为什么查找树并检查是否存在特定值的时间复杂度为O(log(n))，我们如何得到它?

If we have a tree of N elements, why the time complexity of looking up the tree and check if a particular value exists is O(log(n)), how do we get that?

推荐答案

您的问题似乎得到了很好的回答

Your question seems to be well answered here but to summarise in relation to your specific question it might be better to think of it in reverse; "what happens to the BST solution time as the number of nodes goes up"?

基本上，在BST中，每次将节点数量加倍时，解决方案的步骤仅增加一.为了扩展这一点，四倍的节点给出了两个额外的步骤.八倍的节点给出了三个额外的步骤.十六倍的节点给出了四个额外的步骤.依此类推.

Essentially, in a BST every time you double the number of nodes you only increase the number of steps to solution by one. To extend this, four times the nodes gives two extra steps. Eight times the nodes gives three extra steps. Sixteen times the nodes gives four extra steps. And so on.

这些对中第一个数字的以2为底的对数是这些对中的第二个数字.它是以2为底的对数，因为这是一个二进制搜索(您将问题空间减少了一半).

The base 2 log of the first number in these pairs is the second number in these pairs. It's base 2 log because this is a binary search (you halve the problem space each step).

这篇关于为什么在二叉搜索树中查找为O(log(n))?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！