为什么在二进制搜索树中查找是O(log(n))？

Question

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

但是,我不明白时间复杂性的原因O(log(n)).所以,我的问题是:

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

Answer 1

你的问题似乎在这里得到了很好的回答,但总结一下你的具体问题,反思它可能会更好; "随着节点数量的增加,BST解决方案时间会发生什么变化"？

基本上,在每次将节点数量加倍时,在BST中,只需将解决步骤数增加一个.为了扩展这一点,节点的四倍给出了两个额外的步骤.八次节点提供三个额外步骤.节点的十六次提供了四个额外的步骤.等等.

这些对中第一个数字的基数2对数是这些对中的第二个数字.它是基数为2的日志,因为这是一个二进制搜索(每一步将问题空间减半).

Answer 2

这可以很容易地在数学上显示。

在我提出这个之前，让我澄清一些事情。在平衡二叉搜索树中查找或查找的复杂度为 O(log(n))。对于一般的二叉搜索树，它是 O(n)。我将在下面展示两者。

在平衡二叉搜索树中，在最坏的情况下，我要查找的值在树的叶子中。由于 BST 的有序结构，我将基本上从根遍历到叶子，只查看树的每一层一次。因此，我需要做的搜索次数是树的层数。因此，问题归结为找到具有 n 个节点的树的层数的封闭形式表达式。

这是我们将进行简单归纳的地方。只有 1 层的树只有 1 个节点。2 层的树有 1+2 个节点。3 层 1+2+4 节点等。 模式很明确：k 层的树正好有

n=2^0+2^1+...+2^{k-1}

节点。这是一个几何级数，这意味着

n=2^k-1，

相当于：

k = log(n+1)

我们知道 big-oh 对 n 的大值感兴趣，因此常数无关紧要。因此 O(log(n)) 复杂度。

我将给出另一种 - 更短的 - 方式来显示相同​​的结果。因为在寻找一个值时，我们不断地将树分成两半，我们必须这样做 k 次，其中 k 是层数，以下是正确的：

(n+1)/2^k = 1，

这意味着完全相同的结果。你必须说服自己 n+1 中的 +1 来自哪里，但即使你不注意它也没关系，因为我们正在谈论 n 的大值。

现在让我们讨论一般的二叉搜索树。在最坏的情况下，它是完全不平衡的，这意味着它的所有节点只有一个子节点（并且它变成了一个链表）参见例如https://www.cs.auckland.ac.nz/~jmor159/PLDS210/niemann/ s_fig33.gif

在这种情况下，要找到叶子中的值，我需要迭代所有节点，因此 O(n)。

最后要注意的是，这些复杂性不仅适用于查找操作，也适用于插入和删除操作。

（当我达到 10 个代表点时，我将使用更好看的 Latex 数学样式编辑我的方程。所以现在不会让我。）

Answer 3

对我而言，最简单的方法是查看log2（n）的图，其中n是二叉树中的节点数。表格如下：

          log2(n) = d

          log2(1) = 0
          log2(2) = 1 
          log2(4) = 2
          log2(8) = 3
          log2(16)= 4 
          log2(32)= 5
          log2(64)= 6             

然后画一棵小二叉树，这棵树从深度d = 0到d = 3：

            d=0          O
                        / \
            d=1        R   B
                      /\   /\
            d=2      R  B R  B
                    /\ /\ /\ /\
            d=3    R B RB RB R B

因此，当深度d从d = 2变为d = 3时，树中的节点n会有效加倍（例如，当n从7变为15时，n增加8（几乎是一倍）），从而增加n 1.）因此，所需的额外处理量（或所需的时间）仅增加了1次额外的计算（或迭代），因为处理量与d有关。

我们可以看到，在将节点数量加倍之后，我们仅将深度d从d = 2降低到d = 3，仅降低了1个附加级别，以从所有节点n中找到我们想要的节点。这是正确的，因为我们已经搜索了整棵树，需要搜索其中一半以找到所需的节点。

我们可以将其写为d = log2(n)，其中d告诉我们，当树中有n个节点时，要达到树中的任何节点（平均）需要执行多少计算（平均迭代次数）。