在已經失去2個或更多子女之後促銷一個節點

Question

在斐波納契堆的decrease-key操作中，如果允許在切割節點並將其融合到根列表（促銷節點）之前丟失s > 1孩子，是否會改變整體運行時複雜度？我認爲複雜性沒有變化，因爲潛在變化將是相同的。但我不確定我是否正確。

如何通過攤銷分析證明這一點？

Answer 1

改變，在斐波那契堆中一個節點可能會失去兒童的人數確實影響運行時，但我懷疑的是，如果你小心你怎麼做，你仍然會得到相同的漸近運行。

如果您允許每個節點在升級到根目錄之前丟失多個子節點，那麼潛在功能將保持不變。但是，潛在函數並不是Fibonacci堆效率的來源。我們執行級聯剪切（在減少密鑰期間將多個節點提升到根級別的原因）是爲了確保具有次數n的樹具有n箇中指數級數的節點。這樣，當執行出列min操作並將樹合併在一起以使每個訂單至多有一棵樹時，存儲所有節點所需的樹的總數對於節點數是對數的。標準的標記方案保證了n階的每棵樹至少有Θ（φ ^ñ）節點，其中φ是黃金比率（約1.618 ...）

如果允許移出的多個節點每一棵樹之前，他們回到根源，我懷疑是，如果你在一定數量的失蹤孩子上限，你仍然應該得到相同的漸近時間界限，但可能具有較高的常數因子（因爲每棵樹擁有較少的節點因此需要更多的樹木）。如果你想得到一個確切的值，你可以寫出數學來看看每棵樹中節點的數量是多少。

希望這會有所幫助！