森林在不相交數據結構中的組合

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之一。