森林在不相交数据结构中的组合

Question

对于不相交数据 结构的平均情况分析很难做到。问题最少的是答案取决于如何定义平均值（关于联合操作）。例如，下面给出的森林中的 。出于描述目的，每个树是由集合表示的 。

{0}，{1}，{2}，{3}，{4,5，6,8}

我们可以说，由于存在5棵有是5 * 4 = 20 等同于下一个联合的结果（因为任何两棵不同的树 都可以联合）。当然，这个模型的含义是 只有2/5的机会，下一个工会会涉及大型的 树。

另一种模式可能会说，不同树之间的任何两个元素之间的所有联合都是相同的可能性，所以较大的树更有可能参与下一个联合而不是较小的树。在上面的示例 中，有一个8/11的机会，大树参与了 下一个联合，因为（忽略对称）有6种方式合并{1,2,3,4中的两个元素}以及16种方式将 {5,6,7,8}中的元素与{1,2,3,4}中的元素进行合并。还有更多的 模型，并没有就哪个最好而达成共识。运行时间的平均值取决于模型; O（m），O（m log n）和O（mn）边界实际上已经针对三种不同的模型显示，尽管 后面的边界被认为是更现实的。

上面的文本是来自Wessis的算法和数据分析。

我在组合数学上相当差，所以我不了解上面的问题，我在这里需要帮助来回答以下问题。

1. 我们如何得到2/5以上的描述？
2. 我们如何得到8/11在上面的描述？
3. 作者只描述了两个模型，但在段落末尾提到了不同的模型，第三个模型是什么？

感谢您的帮助

Answer 1

下面是前两个问题的答案：

1. 鉴于五棵树A，B，C，d，E什么是E是概率包含在一对随机选择的树中？由于有10对可能（AB，AC，AD，AE，BC，BD，BE，CD，CE，DE）和其中四个（AB，AC，AD，AE）包含A，所以概率为4/10 = 2/5。给定五棵树A = {a}，B = {b}，C = {c}，D = {d}，E = {e，f，g，h}元素的E包含在一对随机选择的项目中（其中没有两个项目是从一棵树中选择的）？

   有22对项目（ab，ac，ad，ae，af，ag，ah，bc，bd，be，bf，bg，bh，cd，ce，cf，cg，ch，de，df ，DG，DH），其中16包括的（E，F，G，H）的概率是16/22 = 8/11之一。