2

如何证明从最小节点开始在 BST 中找到 n-1 次后继是 O(n)？

问题是我们可以创建排序顺序

1）令节点=BST的最小节点。

2) 从那个节点，我们递归调用 find 一个后继节点。

有人告诉我结果是 O(n) 但我不明白也不知道如何证明。

不应该是 O(n*log n) 吗？因为对于步骤 1，它是O(log n)，对于步骤 2，它也是O(log n)但它被称为n-1次。因此，它将是O(n*log n)

请澄清我的疑问。谢谢！:)

4

2 回答 2

4

您是正确的，任何单个操作都可能需要 O(log n) 时间，因此如果您执行这些操作 n 次，您应该获得 O(n log n) 的运行时间。这个界限是正确的，但并不紧密。实际运行时间是 Θ(n)。

看到这一点的一种方法是查看树中的任何单个边缘。如果您从最左边的节点开始并重复执行后继查询，您将访问每条边多少次？如果你仔细观察这些操作是如何工作的，你会发现每条边都被访问了两次：一次向下，一次向上。由于完成的所有工作都是通过上下边完成的，这意味着完成的工作总量与边数的两倍成正比。在任何树中，边数是节点数减一，因此完成的总工作量为 Θ(n)。

为了将其形式化为证明，请尝试证明您永远不会从同一条边下降两次，并且当您上升一条边时，您永远不会再沿​​着该边下降。完成此操作后，运行时间为 Θ(n) 的结论就可以从上述逻辑得出。

希望这可以帮助！

于 2013-09-11T00:53:47.680 回答
4

我想将此作为对 templatetypedef 答案的评论发布，但它太长了。

他的回答是正确的，因为看到这是线性的，最简单的方法是因为每条边都被访问了两次，并且树中的边数总是比节点数少一（因为每个节点都有一个父节点，除了根！）。

问题在于，他对正式证明的表述方式使用了似乎暗示矛盾的词语。一般来说，数学家不赞成使用矛盾，因为它经常产生内容多余的证明。例如：

Proof that  2 + 2 != 5:
Assume for contradiction that 2 + 2 = 5 (<- Remove this line)
Well 2 + 2 = 4
And 4 != 5
Contradiction! (<- Remove this line)

矛盾往往是冗长的，有时甚至会混淆证明背后的想法！有时矛盾似乎非常必要，但相对较少，这是一个单独的讨论。

在这种情况下，我看不出矛盾的证明比直接证明更容易。另一方面，不管证明技术如何，这个证明在形式上都很难看。这是一个尝试：

1)succ(n)算法遍历两条路径之一

  • 在第一种情况下，在从节点到其右子树最左节点的简单路径上访问每条边

  • 在另一种情况下，节点n没有右孩子，在这种情况下，我们沿着它的祖先上升p_1, p_2, p_3, ..., p_k，这p_(k-1)是第一个祖先，它是它的父母的左孩子。所有这些边都在那个简单的路径中访问

我们想证明任意一条边恰好在两次succ()调用中被遍历，一次用于 的第一种情况，succ()一次用于 的第二种情况succ()。好吧，除了最右边的分支之外的每个边缘都是如此，但是您可以单独处理这些边缘情况。或者，我们可以证明更简单的论点，即在访问最后一个元素后返回根

这是双重的，因为对于给定的边e，我们必须找到n1和n2这样succ(n1)遍历e和succ(n2)也遍历e，以及证明每个其他succ()生成的路径不包括e。

2）首先，我们实际上证明对于succ()访问的每种类型的路径，没有两条路径重叠（即如果succ(n)并且succ(n')都遍历相同类型的路径，则这些路径不共享边）

  • 在第一种情况下，简单路径精确定义如下。从节点开始，n向右走一条边到r. 然后遍历以 为根的子树的左分支r。现在考虑从其他节点开始的任何其他此类路径n'（注意，我们不假设n != n'）。它必须右移一个节点到r'。然后它遍历以 为根的子树的最左边的分支r'。如果路径重叠，则选择重叠的边缘之一。如果是，(n,r) = (n',r')那么我们有n = n'，所以它是相同的路径。如果它e = e'在两个最左边的分支中都有一些，那么你可以再次证明n = n'（你可以追踪最左边的分支并显示每条边都是相同的，然后最终得出结论：r = r' => n = n'因为对于一棵树来说，父母是独一无二的。您将在下面看到此跟踪参数）。因此我们知道，对于任何n和n'，如果它们的路径重叠，它们实际上是同一个节点！对立面是这样说的：如果它们是不同的节点，那么它们的路径就不会重叠。这正是我们想要的（相反的总是与原始陈述同样正确）。

  • 在第二种情况下，我们定义从 node 开始的简单路径n，然后沿着祖先向上p_1, p_2, ..., p_k = g直到我们到达第一个节点p_k，p_(k-1)即p_k. n'考虑从节点where开始的其他一些相同类型的路径n != n'。同样它访问p_1', p_2', ..., p_k' = g'. 因为它是一棵树，所以这些祖先中没有一个与第一组相同。因为两条路径上的节点都不相同，所以没有一条边可以相同，因此succ(n)不会succ(n')遍历任何相同的边

3) 现在我们只需要证明对于给定的边，每种类型至少存在一条路径。那么采取任何这样的边缘e = (c,p)（注意这里我忽略了最右边分支上的特殊边缘，这些边缘在技术上只被访问过一次，我也忽略了最左边分支上的特殊边缘，这些边缘在技术上被访问一次find_min()，然后被succ()调用一次）

  • 如果它是从左孩子c到其父母p，那么succ(c)将涵盖第二种类型的路径。要找到另一条路，继续往上走p的祖先p_1, p_2, ..., p_k，p_(k-1)在 的右边p_k。succ(p_k)将遍历包含e定义的路径（因为e它位于子树的最左边的分支上，p_(k-1)它是p_k的右孩子）。

  • 当c的右孩子是p

总结一下我们展示的succ()生成两种路径的证明。对于每种类型的路径，这些类型的所有路径都不重叠。此外，对于任何边缘，我们至少有每种类型的路径中的一种。由于我们调用succ()了每个节点，我们最终可以得出结论，每条边都被遍历了两次（因此算法是Theta(n)）。

尽管这个证明持续了多长时间，但它实际上并不完整（即使我明确表示我正在跳过细节时忽略了要点！）。在某些情况下，我说某物存在而没有证明它存在。您可以根据需要弄清楚这些细节，并且将其完全正确确实很令人满意（至少在我看来。也许当您是天才时，您会发现它很乏味，呵呵）

希望这有帮助。如果您希望我澄清一些步骤，请告诉我

于 2013-09-11T08:43:10.340 回答