PricingLoginStart free
Valmistautuminen ohjelmointihaastatteluihin · Oppitunti

Yhdistäminen rangin mukaan ja käänteisen Ackermannin raja

Lisätkää rankiin perustuva yhdistäminen puiden pitämiseksi matalina ja ymmärtäkää, miksi optimointien yhdistelmä antaa amortisoiduksi ajaksi O(alpha(n)) eli käytännössä vakioajan.

Oppitunti 2/413 vaihetta

Yhdistäminen rangin mukaan ja käänteisen Ackermannin raja on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 2/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.

Miksi puut kasvavat korkeiksi ilman rankia

Pelkkä polun tiivistys estää puita kasvamasta korkeiksi läpikäyntien jälkeen, mutta alkuperäisten union-operaatioiden aikana voimme silti muodostaa korkean puun, jos liitämme aina suuremman puun juuren pienemmän alle. Union by rank ratkaisee tämän seuraamalla puun korkeuden ylärajaa eli rankia ja liittämällä matalamman puun aina syvemmän puun alle.

Rank ei ole täsmälleen sama kuin korkeus — polun tiivistys voi pienentää korkeuden rankia pienemmäksi — mutta se on yläraja. Kun syvempi puu säilytetään uutena juurena, rank kasvaa vain silloin, kun kaksi saman rankin puuta yhdistetään. Näin suurin mahdollinen rank rajoittuu arvoon O(log n).

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n   # initially all trees have rank 0

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        # Attach lower-rank tree under higher-rank tree
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1   # only increases when ranks are equal
        return True

Union by rank -menetelmän kolme tapausta

Kun yhdistämme kaksi komponenttia, joiden juuret ovat px ja py, rankien perusteella syntyy kolme tapausta:

  • rank[px] > rank[py]: liitä py px:n alle — px:n rank ei muutu
  • rank[px] < rank[py]: liitä px py:n alle — py:n rank ei muutu
  • rank[px] == rank[py]: liitä py px:n alle (tai päinvastoin) — uuden juuren rank kasvaa yhdellä

Rank kasvaa vain saman rankin tapauksessa. Tämä tarkoittaa, että rank n edellyttää vähintään 2^n solmua, joten suurin rank on O(log n). Näin find-polut pysyvät lyhyinä myös ilman polun tiivistystä.

# Illustrating rank behaviour with 8 nodes
dsu_parent = list(range(8))
dsu_rank = [0] * 8

def find(x):
    while dsu_parent[x] != x:
        x = dsu_parent[x]
    return x

def union(x, y):
    px, py = find(x), find(y)
    if px == py: return
    if dsu_rank[px] < dsu_rank[py]:
        px, py = py, px
    dsu_parent[py] = px
    if dsu_rank[px] == dsu_rank[py]:
        dsu_rank[px] += 1

# Build balanced tree step by step
union(0,1); union(2,3); union(4,5); union(6,7)
union(0,2); union(4,6)
union(0,4)
print('Ranks:', dsu_rank)    # max rank <= log2(8) = 3
print('Root of all:', find(0))

Polun tiivistyksen ja union by rank -menetelmän yhdistelmä

Kun sekä polun tiivistystä että union by rank -menetelmää käytetään yhdessä, operaation amortisoitu aikavaativuus pienenee arvoon O(alpha(n)) — käänteisen Ackermannin funktion aikavaativuuteen. Kaikilla käytännöllisillä syötteen koolla (enintään 2^65536) alpha(n) on korkeintaan 4. Tämä on käytännössä vakioaikaista.

Polun tiivistys litistää puut alhaalta ylöspäin läpikäyntien jälkeen, kun taas union by rank estää puita kasvamasta korkeiksi ylhäältä alaspäin yhdistämisten aikana. Menetelmät täydentävät toisiaan: rank rajoittaa alkuperäistä syvyyttä, ja tiivistys poistaa tämän syvyyden ensimmäisen läpikäynnin jälkeen.

class OptimalDSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):                        # path compression
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):                    # union by rank
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

dsu = OptimalDSU(1000)
import random; random.seed(42)
for _ in range(5000):
    dsu.union(random.randint(0,999), random.randint(0,999))
print('Max rank reached:', max(dsu.rank))  # stays very small

Käänteisen Ackermannin funktion ymmärtäminen

Ackermannin funktio A(m, n) kasvaa poikkeuksellisen nopeasti — nopeammin kuin mikään primitiivirekursiivinen funktio. Sen käänteinen funktio alpha(n) määritellään pienimmäksi m:ksi, jolle A(m, m) >= n. Koska Ackermannin funktio kasvaa niin nopeasti, alpha(n) kasvaa käsittämättömän hitaasti.

Kun n = 10^80 eli havaittavan maailmankaikkeuden atomien määrä, alpha(n) on edelleen vain 4. Siksi molempien optimointien kanssa käytettävää DSU:ta pidetään käytännössä vakioaikaisena kaikissa käytännön tilanteissa. Et tule koskaan kohtaamaan todellista ongelmaa, joka olisi riittävän suuri kasvattaakseen alpha(n):n yli arvon 5.

# Showing how slowly alpha(n) grows
# alpha(n) = smallest m such that A(m,m) >= n
# A(0,n) = n+1
# A(1,n) = n+2
# A(2,n) = 2n+3
# A(3,n) = 2^(n+3) - 3
# A(4,4) = 2^(2^(2^(2^2))) - 3 which is astronomically large

alpha_thresholds = {
    1: 'n=1',
    2: 'n up to 3',
    3: 'n up to about 2048',
    4: 'n up to 10^19728 (far beyond atoms in universe)',
    5: 'essentially unreachable in practice',
}
for k, v in alpha_thresholds.items():
    print(f'alpha(n)={k}: {v}')
print('\nConclusion: DSU operations are effectively O(1) for all real inputs.')

Rank vai koko: kumpaa kannattaa käyttää?

Vaihtoehto union by rank -menetelmälle on union by size -menetelmä, jossa pienemmän koon puu liitetään aina suuremman koon puun alle. Molemmat lähestymistavat takaavat puun korkeudeksi O(log n). Union by size -menetelmää on usein helpompi hahmottaa, koska koot ovat tarkkoja lukumääriä, kun taas rankit ovat ylärajoja eivätkä välttämättä kuvaa todellista korkeutta tiivistyksen jälkeen.

Haastatteluissa kumpikin lähestymistapa on hyväksyttävä. Union by size tarjoaa lisäksi komponenttien koot ilman lisäkustannuksia, ja monet tehtävät edellyttävät juuri niitä. Union by rank on hieman elegantimpi teoreettisesti ja vastaa Tarjanin alkuperäistä käänteisen Ackermannin funktion rajaa koskevaa todistusta.

class DSUBySize:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.size[px] < self.size[py]:
            px, py = py, px       # always attach smaller under larger
        self.parent[py] = px
        self.size[px] += self.size[py]
        return True

dsu = DSUBySize(8)
for u, v in [(0,1),(2,3),(0,2),(4,5),(6,7),(4,6),(0,4)]:
    dsu.union(u, v)
print('Size of giant component:', dsu.size[dsu.find(0)])

Todistuksen pääidea: miksi rank pysyy arvossa O(log n)

Voimme todistaa induktiolla, että DSU-puu, jonka rank on r, sisältää vähintään 2^r solmua. Perustapaus: rank 0 tarkoittaa yhtä solmua (2^0 = 1). Induktioaskel: rank r kasvaa vain, kun kaksi rankin r-1 puuta yhdistetään. Induktio-oletuksen mukaan kummassakin alipuussa on vähintään 2^(r-1) solmua, joten yhdistetyssä puussa on vähintään 2 × 2^(r-1) = 2^r solmua.

Koska rankin r puussa on vähintään 2^r solmua ja solmuja on yhteensä n, suurin rank on korkeintaan log₂(n). Tämä tarkoittaa, että find-operaation aikavaativuus ilman polun tiivistystä on O(log n), ja polun tiivistyksen kanssa amortisoitu kustannus pienenee huomattavasti enemmän.

# Verify the 2^rank lower bound empirically
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.size = [1] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return
        if self.rank[px] < self.rank[py]: px, py = py, px
        self.parent[py] = px
        self.size[px] += self.size[py]
        if self.rank[px] == self.rank[py]: self.rank[px] += 1

n = 32
dsu = DSU(n)
for i in range(n - 1): dsu.union(i, i + 1)
for root in range(n):
    if dsu.find(root) == root:
        r = dsu.rank[root]
        print(f'Root {root}: rank={r}, size={dsu.size[root]}, 2^rank={2**r}')

DSU-malli kilpailuohjelmointiin

Kilpailuohjelmoinnissa ja työhaastatteluissa tarvitset hyväksi koetellun DSU-mallin, joka on lyhyt, oikeellinen ja käsittelee kaikki reunatapaukset. Alla oleva malli käyttää polun puolitusta (yhden läpikäynnin tiivistystä) yhdessä union by size -menetelmän kanssa. Tämä yhdistelmä on helppo kirjoittaa nopeasti, eikä se käytä lainkaan rekursiota.

Alusta aina parent[i] = i ja size[i] = 1. Muista, että find-operaation jälkeen juuren size kuvaa koko komponentin kokoa. Älä koskaan käytä suoraan arvoa size[x] — kutsu aina size[find(x)].

class DSU:
    def __init__(self, n):
        self.p = list(range(n))
        self.sz = [1] * n

    def find(self, x):
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]   # path halving
            x = self.p[x]
        return x

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return False
        if self.sz[x] < self.sz[y]: x, y = y, x
        self.p[y] = x
        self.sz[x] += self.sz[y]
        return True

    def same(self, x, y): return self.find(x) == self.find(y)
    def size(self, x): return self.sz[self.find(x)]

# Usage
dsu = DSU(10)
dsu.union(0, 5)
dsu.union(5, 9)
print(dsu.same(0, 9))   # True
print(dsu.size(0))       # 3

Milloin DSU ei riitä

DSU tukee joukkojen yhdistämistä, mutta se ei tue joukon jakamista takaisin kahdeksi. Jos tehtävässä tarvitaan sekä ryhmien yhdistämistä että erottamista, tarvitset toisen tietorakenteen, kuten link-cut treen. DSU ei myöskään luonnostaan tallenna kunkin ryhmän alkioita — sitä varten tarvitset erillisen vierekkäisyyslistan tai sanakirjan.

Lisäksi tavallinen DSU ei tue painotettuja kaaria ilman muutoksia (weighted DSU on kehittyneempi muunnelma). Tehtävissä, joissa etsitään halvinta polkua yhteydessä olevien solmujen välillä, Dijkstra tai BFS on sopivampi. DSU:n rajoitusten tunnistaminen auttaa välttämään sen vääränlaisen soveltamisen.

# DSU is perfect for: connected-components, cycle detection,
# Kruskal's MST, accounts-merge, number-of-provinces

# DSU is NOT suitable for:
# - Splitting/removing edges from a group
# - Finding the actual path between two nodes
# - Storing all members of a group efficiently
# - Directed graphs (without modification)

# Example of storing group members alongside DSU
from collections import defaultdict

class DSUWithMembers:
    def __init__(self, n):
        self.p = list(range(n))
        self.members = defaultdict(set)
        for i in range(n): self.members[i].add(i)

    def find(self, x):
        while self.p[x] != x: self.p[x] = self.p[self.p[x]]; x = self.p[x]
        return x

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return
        self.members[px] |= self.members[py]
        del self.members[py]
        self.p[py] = px

DSU:n, BFS:n ja DFS:n vertailu yhteyksien tarkistamiseen

Sekä BFS/DFS että DSU ratkaisevat staattisia yhteyksien tarkistuskyselyjä, mutta niillä on erilaiset vahvuudet. BFS/DFS toimii ajassa O(V + E) ja pystyy löytämään solmujen välisen todellisen polun. DSU vastaa moniin yhteyskyselyihin asteittain kasvavilla särmäjoukoilla lähes ajassa O(1) kyselyä kohden — se sopii erinomaisesti online-algoritmeihin, joissa särmät saapuvat yksi kerrallaan.

Jos saatte kaikki särmät etukäteen ja tarvitsette vain tiedon yhteyksistä, kumpikin menetelmä toimii. Jos särmät saapuvat dynaamisesti ja yhteyskyselyihin on vastattava jokaisen uuden särmän jälkeen, DSU on selvästi parempi vaihtoehto. Jos ongelmassa tarvitaan myös lyhin polku, käyttäkää BFS:ää.

# Comparing DSU vs BFS for 1000 nodes, 2000 edges
# After all edges given => BFS works fine
# But with online edge arrival + interleaved queries => DSU shines

from collections import deque

def bfs_connected(graph, src, dst, n):
    visited = set([src])
    q = deque([src])
    while q:
        node = q.popleft()
        if node == dst: return True
        for nb in graph.get(node, []):
            if nb not in visited:
                visited.add(nb); q.append(nb)
    return False

# DSU for same query:
# dsu.same(src, dst) -- O(alpha(n)) amortised
# BFS for same query:
# O(V + E) every time -- not suitable for repeated queries
print('DSU is preferred for repeated connectivity queries.')
print('BFS/DFS is preferred when you also need the actual path.')

Harjoitus: pienin virittävä puu DSU:n avulla

Kruskalin algoritmi pienimmän virittävän puun löytämiseen käyttää suoraan DSU:ta. Järjestäkää kaikki särmät painon mukaan ja lisätkää sitten ahneesti jokainen särmä, jonka päätepisteet ovat eri komponenteissa eli joka ei muodosta sykliä. DSU tekee syklin tarkistuksen lähes ajassa O(1). Tuloksena on n-1 särmää sisältävä MST.

Tämä on klassinen esimerkki DSU:n tehokkuudesta: se muuttaa naiiviin syklin tarkistukseen kuluvan ajan O(E × V) prosessiksi, jonka aikavaativuus on O(E × alpha(n)). Kun särmät lajitellaan ajassa E log E, Kruskalin algoritmin kokonaisaikavaativuus on O(E log E), ja DSU-operaatiot ovat niin nopeita, että niiden vaikutus lajitteluun verrattuna on mitätön.

def kruskal(n, edges):
    edges.sort(key=lambda e: e[2])  # sort by weight
    parent = list(range(n))
    rank = [0] * n

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        px, py = find(x), find(y)
        if px == py: return False
        if rank[px] < rank[py]: px, py = py, px
        parent[py] = px
        if rank[px] == rank[py]: rank[px] += 1
        return True

    mst_weight = 0
    mst_edges = []
    for u, v, w in edges:
        if union(u, v):
            mst_weight += w
            mst_edges.append((u, v, w))
    return mst_weight, mst_edges

edges = [(0,1,4),(0,2,3),(1,2,1),(1,3,2),(2,3,5)]
w, e = kruskal(4, edges)
print('MST weight:', w)   # 6: edges (1,2,1)+(1,3,2)+(0,2,3)
print('MST edges:', e)

Palautusta käyttävä DSU: offline-yhteyksien tarkistaminen

Tavallinen DSU ei tue toimintojen kumoamista. Palautusta käyttävä DSU (jota kutsutaan myös historiaa käyttäväksi DSU:ksi) tukee sitä: polkujen pakkauksen sijaan, koska sen kumoaminen on hankalaa, käytetään vain rankin mukaista yhdistämistä ja jokainen yhdistäminen tallennetaan pinoon. Palautusta varten pinosta poistetaan alkio ja vanhempi- sekä rank-tiedot palautetaan. Näin voidaan ratkaista offline-dynaamisia yhteysongelmia, joissa särmiä voidaan lisätä ja poistaa.

Vaikka tämä on edistynyt muunnelma, jota nähdään harvoin tavallisissa työhaastatteluissa, se osoittaa, että rankin mukainen yhdistäminen on keskeinen invariantti — ei polkujen pakkaus. Ilman polkujen pakkausta jokainen find-operaatio vie ajan O(log n), ja palautuksen yhteydessä pinotoiminnot vievät ajan O(1). Näin kokonaisaikavaativuus on O(log n) operaatiota kohden O(alpha(n)):n sijaan.

class DSUWithRollback:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.history = []   # stack of (node, old_parent, node2, old_rank)

    def find(self, x):    # NO path compression (cannot undo)
        while self.parent[x] != x:
            x = self.parent[x]
        return x

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return False
        if self.rank[px] < self.rank[py]: px, py = py, px
        # Record state before modifying
        self.history.append((py, self.parent[py], px, self.rank[px]))
        self.parent[py] = px
        if self.rank[px] == self.rank[py]: self.rank[px] += 1
        return True

    def rollback(self):
        py, old_par_py, px, old_rank_px = self.history.pop()
        self.parent[py] = old_par_py
        self.rank[px] = old_rank_px

dsu = DSUWithRollback(5)
dsu.union(0, 1); dsu.union(1, 2)
print('0 and 2 connected:', dsu.find(0) == dsu.find(2))  # True
dsu.rollback()
print('After rollback:', dsu.find(0) == dsu.find(2))     # False

Pikatesti

Testatkaa ymmärrystänne tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -kokonaisuuden käsitteistä.

Vastaa interaktiivisessa oppitunnissa

Oppitunnin yhteenveto

Tässä oppitunnissa opitte: rankin mukainen yhdistäminen liittää aina matalamman puun korkeamman puun alle, rank kasvaa vain, kun kaksi saman rankin puuta yhdistyy, joten puun korkeus pysyy arvossa O(log n), ja polkujen pakkauksen yhdistäminen rankin mukaiseen yhdistämiseen tuottaa jaksotetun O(alpha(n))-aikavaativuuden — käytännössä vakioajan. Seuraavaksi sovellamme optimaalista DSU:ta ylimääräisten yhteyksien ja graafien syklien tunnistamiseen.

Aloita maksutta

Opi Valmistautuminen ohjelmointihaastatteluihin tekoälytuutorin avulla — ilmaiseksi

Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.

Kurssit
90
Oppitunnit
360
Aloita opiskelu maksuttaNäytä koko kurssi

Usein kysytyt kysymykset

Onko oppitunti ”Yhdistäminen rangin mukaan ja käänteisen Ackermannin raja” ilmainen?

Kyllä – oppitunnin ”Yhdistäminen rangin mukaan ja käänteisen Ackermannin raja” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.

Mitä opin oppitunnilla ”Yhdistäminen rangin mukaan ja käänteisen Ackermannin raja”?

Lisätkää rankiin perustuva yhdistäminen puiden pitämiseksi matalina ja ymmärtäkää, miksi optimointien yhdistelmä antaa amortisoiduksi ajaksi O(alpha(n)) eli käytännössä vakioajan. Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.

Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?

Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 2/4.

Kuinka kauan ”Yhdistäminen rangin mukaan ja käänteisen Ackermannin raja”-oppitunnin suorittaminen kestää?

Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.

Voinko kirjoittaa ja suorittaa koodia tällä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?

Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.

Kaikki tämän kurssin oppitunnit

  1. DSU polkujen tiivistyksellä
  2. Yhdistäminen rangin mukaan ja käänteisen Ackermannin raja
  3. Redundant Connection ja syklien tunnistus
  4. Accounts Merge ja yhtenäiset komponentit
← Takaisin: Valmistautuminen ohjelmointihaastatteluihin