logo标签列表

为什么在二叉搜索树中查找的时间复杂度是O(log(n))?

data-structurestime-complexitybig-obinary-search-tree
33

我可以看出，在二叉搜索树中查找值时，每次将树的一半与我们正在寻找的值进行比较。

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

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

5个回答
50
您的问题似乎在这里有很好的答案，但为了总结与您特定问题相关的内容，最好反过来思考；"二叉搜索树解决方案时间随节点数量增加会发生什么"？
基本上，在BST中，每当您将节点数量翻倍时，解决方案步骤的数量只会增加一步。扩展此概念，四倍节点增加两步。八倍节点增加三步。十六倍节点增加四步。以此类推。
这些配对中第一个数字的2为底对数等于第二个数字。这是因为这是二进制搜索（每步将问题空间减半）。
11
哇塞，你解释得太好了，我几秒钟就理解原因了。谢谢！ - Himel Das
21

对我来说最简单的方法是查看log2(n)的图表，其中n是二叉树中节点的数量。以表格的形式呈现如下：

对我而言，最简单的方法是查看 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

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

我们可以看到，我们只需在深度d下降1级，从d=2降至d=3，即可找到我们想要的节点，而节点数翻倍了。这是因为我们现在搜索了整棵树，至少我们需要搜索一半才能找到我们想要的节点。

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

16

这可以很容易地用数学来证明。

在我介绍它之前，让我澄清一些问题。在平衡二叉搜索树中查找的复杂度是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)

我们知道大O符号涉及到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数学样式编辑我的方程式。现在SO不让我这样做。）

3
每当你看到一个运行时间中有O(log n)的因子时，很有可能你正在看"通过一个常数不断地缩小某个对象的大小"这种形式的东西。 因此，最好的方式是将这个问题想象成 - 当你在二叉搜索树中查找时，到底是哪些内容被常数因子缩小了，这个常数是什么？
首先，让我们想象一下你有一棵完美平衡的二叉树，像这样：
                     *
              /             \
             *               *
          /     \         /     \
         *       *       *       *
        / \     / \     / \     / \
       *   *   *   *   *   *   *   *

在进行搜索时，每个节点都会被检查。如果它是你要找的节点，那太好了！你已经完成了。另一方面，如果不是，则要进入左子树或右子树，然后重复此过程。
如果进入其中一个子树，实际上就意味着“我完全不关心那个子树中的内容。” 你扔掉了其中的所有节点。那里有多少个节点？通过快速的视觉检查 - 理想情况下还要加上一些漂亮的数学计算 - 你会发现你正在丢弃树中约一半的节点。
这意味着在查找的每个步骤中，你要么（1）找到你要查找的节点，要么（2）扔掉树中一半的节点。由于每个步骤都需要做固定量的工作，因此你正在看到 O(log n) 行为的标志性行为 - 工作量在每个步骤中以恒定因子下降，因此只能对其进行对数次操作。
现在当然，并不是所有的树都长这样。AVL树有一个有趣的特性，每次你进入一个子树时，你会抛弃大约黄金比例分数的总节点数。因此，这保证了在用尽节点之前，你只能进行对数次步骤-因此高度为O(log n)。在红黑树中，每一步都会扔掉（大约）四分之一的总节点数，由于你正在以一个常数因子缩小，所以你再次得到了期望的O(log n)查找时间。非常有趣的替罪羊树有一个可调参数，用于确定它有多紧密平衡，但是你可以展示出，你采取的每一步都会根据这个可调参数抛弃一些常数因子，从而获得O(log n)的查找效率。
然而，这种分析在不平衡的树中会失效。如果你有一棵完全退化的树——每个节点都只有一个子节点——那么你走下树的每一步只会扔掉一个节点，而不是一个常数分数。这意味着，在最坏情况下，查找时间会达到O(n)，因为你可以从n中“减去”一个常数的次数是O(n)。
3
如果我们有一个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))的时间复杂度。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接