不帶路徑壓縮的森林實現的不相交集合

考慮具有n個不同元素的加權聯合啓發式（NO PATH COMPRESSION！）的森林實現不相交集合。將T（n，m）定義爲執行n-1個聯合序列的最壞情況時間複雜度，m以任何順序發現，其中m是任何大於n的正整數。不帶路徑壓縮的森林實現的不相交集合

我將T（n，m）定義爲執行n-1個聯合的序列，然後m找到AFTERWARDS，因爲在可能的最大樹上執行查找操作將花費最長的時間。因此，T（n，m）= m * log（n）+ n - 1，因爲每個聯合都取O（1），因此n-1聯合是n-1個步驟，並且每個find都需要log（n） n-1個聯合之後的合成樹的高度由log_2（n）限定。

我現在的問題是，T（n，m）選擇看起來不錯？其次，T（n，m）是大Ω（m * log（n））？我的觀點是，假設最小可能的T（n，m）是m * log（2）+1，明顯大於m * log（2），那麼它是c = 1且n> = 2。似乎很愚蠢的問這個問題，但是解決方案似乎相當容易，所以我對我的正確性有懷疑。

在此先感謝。

來源

2011-03-11 Dee Em.

我們只處理攤銷分析嗎？除非我錯了，沒有路徑壓縮，最壞的情況下查找時間可能是O（n）。 – efficiencyIsBliss 2011-03-11 04:39:18

@ efficiencyIsBliss-如果你通過重量進行聯合，你確實可以做出這個O（lg n）。這個想法是，每次你增加一個路徑的高度時，你必須加倍節點的數量。 – templatetypedef 2011-03-11 06:47:11

是的T（n，m）看起來很好，但我想你可以給出一個正式的歸納證明，最糟糕的情況是工會跟隨發現。

至於證明T（N，M）爲Ω（米的log（n）），則需要以表明存在n個且m 和c，使得對所有的n≥Ñ_{0（n，m）≥cmlog（n）。你寫的東西可以證明這隻適用於n = 2。}

來源

2011-03-11 23:39:37 user635541

不帶路徑壓縮的森林實現的不相交集合

回答

相關問題