In Tree-based Implementation of Union Find-bewerking wordt elk element opgeslagen in een knooppunt, dat een verwijzing naar een setnaam bevat. Een knooppunt v waarvan de setpointer terug naar v wijst, is ook een setnaam. Elke set is een boom, geworteld in een knoop met een zelfverwijzende setpointer.
Om een unie uit te voeren, laten we eenvoudig de wortel van de ene boom naar de wortel van de andere wijzen. Om een zoekopdracht uit te voeren, volgen we setnaamwijzers vanaf het startknooppunt totdat we een knooppunt bereiken waarvan de ingestelde naamwijzer naar zichzelf verwijst.
In Union op maat -> Bij het uitvoeren van een unie maken we de wortel van een kleinere boom
wijs naar de wortel van de grotere. Dit impliceert O(n log n) tijd voor
het uitvoeren van n union find-bewerkingen. Elke keer dat we een aanwijzer volgen, gaan we naar een subboom met een grootte die maximaal twee keer zo groot is als de vorige subboom. We zullen dus maximaal O(log n)-aanwijzingen volgen voor elke vondst.
Ik begrijp niet hoe voor elke samenvoegbewerking de zoekbewerking altijd O(log n) is. Kan iemand uitleggen hoe de worst case complexiteit eigenlijk wordt berekend?
Antwoord 1, autoriteit 100%
Laten we voorlopig aannemen dat elke boom met hoogte h ten minste 2^h knopen bevat. Wat gebeurt er als je twee van zulke bomen samenvoegt?
Als ze van verschillende grootte zijn, is de hoogte van de gecombineerde boom hetzelfde als de hoogte van de hogere, dus heeft de nieuwe boom nog steeds meer dan 2^h knooppunten (dezelfde hoogte maar meer knooppunten).
Als ze nu dezelfde hoogte hebben, zal de resulterende boom zijn hoogte met één verhogen en zal minstens 2^h + 2^h = 2^(h+1) knooppunten bevatten. Dus de voorwaarde blijft bestaan.
De meest elementaire bomen (1 knoop, hoogte 0) voldoen ook aan de voorwaarde. Hieruit volgt dat alle bomen die kunnen worden geconstrueerd door twee bomen samen te voegen, hieraan ook voldoen.
Nu is de hoogte slechts het maximale aantal stappen dat moet worden gevolgd tijdens een vondst. Als een boom n knopen heeft en hoogte h (n >= 2^h) geeft dit onmiddellijk log2(n) >= h >= stappen.
Antwoord 2, autoriteit 50%
We moeten bewijzen dat de maximale hoogte van bomen log(N) is, waarbij N het aantal items is in UF (1)
In het basisscenario hebben alle bomen een hoogte van 0. (1)natuurlijk tevreden
Ervan uitgaande dat alle bomen voldoen aan (1) moeten we bewijzen dat het samenvoegen van 2 bomen met i, j (i <= j) knooppunten een nieuwe boom zal creëren met een maximale hoogte log(i + j)(2):
Omdat de procedure voor het samenvoegen van 2 bomen de wortelknoop van de kleinere boom krijgt en deze aan de wortelknoop van de grotere bevestigt, zodat de hoogte van de nieuwe boom:
max(log(j), 1 + log(i)) = max(log(j), log(2i)) <= log(i + j) => (2) proved
- log(j): hoogte van de nieuwe boom is nog steeds de hoogte van de grotere boom
- 1 + log(i): wanneer de hoogte van 2 bomen hetzelfde is
Zie de afbeelding hieronder voor meer details:
Naslagwerk: Algoritmen
Antwoord 3
U kunt n union find-bewerkingen (union by rank of size) uitvoeren met complexiteit O(n lg* n)waarbij lg* n is de inverse Ackermann-functiemet behulp van optimalisatie van padcompressie.
Merk op dat o (n lg * n) beter is dan o (n log n)
in de vraag Waarom is de Ackermann-functie gerelateerd aan de geamortiseerde complexiteit van Union-Find Algoritme die wordt gebruikt voor Disjunct-sets? vindt u details over deze relatie.