27

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

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

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

4

5 回答 5

43

您的问题似乎在这里得到了很好的回答，但总结一下您的具体问题，最好反过来考虑它；“随着节点数量的增加，BST 求解时间会发生什么变化”？

本质上，在 BST 中，每次将节点数量增加一倍时，您只会将求解的步骤数增加一倍。为了扩展这一点，四倍的节点给出了两个额外的步骤。八倍的节点给出了三个额外的步骤。十六倍的节点给出了四个额外的步骤。等等。

这些对中第一个数字的以 2 为底的对数是这些对中的第二个数字。它是基于 2 的日志，因为这是一个二进制搜索（每一步都将问题空间减半）。

于 2013-01-20T17:10:09.170 回答
13

对我来说，最简单的方法是查看 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 有效地翻倍（例如，当深度 d 从 7 变为 15 时，n 增加 8 到 d=3，增加1.) 因此，所需的额外处理量（或所需时间）仅增加1次额外计算（或迭代），因为处理量与 d 有关。

我们可以看到，在将节点数加倍后，我们只向下增加了 1 级深度 d，从 d=2 到 d=3，以在所有节点 n 中找到我们想要的节点。这是真的，因为我们现在已经搜索了整个树，嗯，我们需要搜索的一半来找到我们想要的节点。

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

于 2017-06-13T13:57:40.027 回答
8

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

在我介绍之前，让我澄清一些事情。在平衡二叉搜索树中查找或查找的复杂度为 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 数学样式编辑我的方程式。所以现在不会让我这样做。）

于 2017-11-03T01:10:12.937 回答
2

每当您看到其中包含 O(log n) 因子的运行时，您很有可能正在查看“不断将某个对象的大小除以一个常数”形式的内容。所以思考这个问题的最好方法可能是——当你在二叉搜索树中进行查找时，究竟是什么被一个常数因子削减了，这个常数究竟是什么？

首先，让我们假设您有一个完美平衡的二叉树，如下所示：

                     *
              /             \
             *               *
          /     \         /     \
         *       *       *       *
        / \     / \     / \     / \
       *   *   *   *   *   *   *   *

在进行搜索的每一点，您都会查看当前节点。如果它是您正在寻找的那个，那就太好了！你完全完成了。另一方面，如果不是，那么你要么下降到左子树或右子树，然后重复这个过程。

如果你走进两个子树中的一个，你实际上是在说“我根本不关心另一个子树中有什么”。你把里面的所有节点都扔掉了。那里有多少个节点？好吧，通过快速的目视检查 - 理想情况下，随后进行一些很好的数学运算 - 你会发现你正在丢弃树中大约一半的节点。

这意味着在查找的每一步中，您要么 (1) 找到您要查找的节点，要么 (2) 丢弃树中的一半节点。由于您在每一步都在做恒定的工作量，因此您正在查看 O(log n) 行为的标志性行为 - 每一步的工作量都会下降一个常数因子，因此它只能以对数方式进行多次次。

当然，并不是所有的树都是这样的。AVL 树有一个有趣的特性，即每次下降到子树时，您都会丢弃总节点的大致黄金比例部分。因此，这可以保证您在用完节点之前只能采取对数许多步骤 - 因此 O(log n) 高度。在红/黑树中，每一步都会丢弃（大约）四分之一的总节点，并且由于您缩小了一个常数因子，您再次获得了您想要的 O(log n) 查找时间。非常有趣的替罪羊树有一个可调参数，用于确定它的平衡程度，但您可以再次证明，您采取的每一步都会根据这个可调参数丢弃一些常数因子，给出 O(log n) 查找。

然而，这种分析对于不平衡的树来说是错误的。如果你有一棵纯粹的退化树——每个节点都只有一个子节点——那么你沿着树向下走的每一步只会扔掉一个节点，而不是一个恒定的分数。这意味着在最坏的情况下查找时间会达到 O(n)，因为从 n 中减去常数的次数是 O(n)。

于 2017-11-03T01:22:56.780 回答
2

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

那不是真的。默认情况下，二叉搜索树中的查找不是O(log(n))，其中n是节点数。在最坏的情况下，它可能变成O(n). 例如，如果我们插入以下序列的值n, n - 1, ..., 1（以相同的顺序），那么树将表示如下：

                  n
                 /
              n - 1
               /
            n - 2
             /
           ...
           1

查找具有值的节点1具有O(n)时间复杂度。

为了使查找更有效，树必须平衡，使其最大高度与 成正比log(n)。在这种情况下，查找的时间复杂度是O(log(n))因为查找任何叶子都受log(n)操作限制。

但同样，并非每个二叉搜索树都是平衡二叉搜索树。您必须平衡它以保证O(log(n))时间复杂度。

于 2019-12-17T19:59:38.820 回答