我正在阅读 Robert Segdewick 在 C++ 中的算法中关于随机二叉搜索树的内容。
随机数生成器仍然有机会在每次机会时都做出错误的决定，从而使我们的树不平衡，但我们可以从数学上分析这种机会并证明它微乎其微。
属性(property) 13.2。 : 随机 BST 的构造成本大于 α 倍平均值的概率小于 e-α
例如，构建 100,000 个节点的随机 BST 需要大约 230 万次比较，但比较次数超过 2300 万次的概率远低于 0.01%。这样的性能保证足以满足处理这种规模的真实数据集的实际需求。当为这样的任务使用标准 BST 时，我们不能提供这样的保证:例如，如果数据中有重要的顺序，我们会遇到性能问题，这在随机数据中不太可能，但在实际中肯定不会不寻常数据，出于多种原因。
类似于属性 13.2 的结果也适用于快速排序的运行时间，通过相同的论证。但是这里的结果更重要，因为它也意味着在树中搜索的成本接近于平均值。不管构建树的任何额外成本，我们都可以使用标准的 BST 实现来执行搜索操作，成本仅取决于树的形状，而根本没有额外的平衡成本。此属性在典型应用程序中很重要，在这些应用程序中，搜索操作比其他任何操作都多得多。例如，上一段中描述的 100,000 个节点的 BST 可能包含一个电话簿，并且可能用于数百万次搜索。我们几乎可以肯定，每次搜索都会在大约 23 次比较的平均成本的一个小常数因子内，并且出于实际目的，我们不必担心大量搜索的成本接近 100,000 的可能性比较，而对于标准 BST，我们需要关注。
我对以上文字的问题是
- 作者所说的“我们几乎可以肯定每次搜索都在大约 23 次比较的平均成本的一个小常数因子之内，并且出于实际目的”是什么意思？这里什么是小常数。
谢谢
最佳答案
好吧，您已经提到了快速排序，这是此类算法的完美示例。 Quicksort 的最坏情况性能为 O(N^2)。然而，它是全世界使用最广泛的排序算法之一。
为什么要使用这样的算法？ 因为最坏的情况真的很少见。非常罕见，即使它出现一两次也值得使用该算法。它可能比保证解决方案更容易实现，它可以与当代硬件(缓存)等更好地协作。
通常使用快速排序比堆排序更好，尽管理论上堆排序更好(消耗 O(1) 额外内存和 O(N log N) 时间在最坏的情况下)。
因此，在我看来，这本书想说的是，即使情况不妙，随机 BST 也值得使用。仅仅是因为这种情况的可能性真的非常低。在实时系统的关键部分使用这样的结构不是一个好主意。但是，对于普通应用程序，使用随机结构可能会有所帮助。因为和自平衡树一样好的概率是相当高的。因为你节省了很多时间而不是编码自平衡。 CPU 时间很便宜，开发人员的时间很贵。
就个人而言，我在编写 union-find 代码时使用随机方法。为了保证最坏情况的复杂性，您应该将较小的集合加入较大的集合，我是随机进行的。它节省了几行代码和一些内存，而且在实践中我没有注意到随机版本和保证版本之间的区别。
关于algorithm - 随机 bst 分析，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23608258/