Dereceye Göre Birleştirme ve Ters Ackermann Sınırı
Ağaçları sığ tutmak için dereceye dayalı birleştirme ekleyin ve birleşik optimizasyonların neden amorti edilmiş O(alpha(n)) — fiilen sabit — süre verdiğini anlayın.
Dereceye Göre Birleştirme ve Ters Ackermann Sınırı, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 2. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.
Derece Olmadan Ağaçlar Neden Uzunlaşır
Yalın yol sıkıştırması, dolaşmalardan sonra uzun ağaçları önler; ancak ilk union işlemleri sırasında, büyük ağacın kökünü her zaman küçük ağacın altına bağlarsak yine uzun bir ağaç oluşturabiliriz. Dereceye göre birleştirme, ağaç yüksekliğinin üst sınırını (dereceyi) izleyerek ve sığ ağacı her zaman derin ağacın altına bağlayarak bu sorunu çözer.
Derece tam olarak yükseklik değildir; yol sıkıştırması yüksekliği dereceden daha küçük hâle getirebilir. Ancak derece bir üst sınırdır. Daha derin ağacı yeni kök olarak koruyarak derecenin yalnızca dereceleri eşit olan iki ağaç birleştiğinde artmasını sağlarız; böylece en büyük derece O(log n) ile sınırlanır.
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 TrueDereceye Göre Birleştirmenin Üç Durumu
Kökleri px ve py olan iki bileşen birleştirilirken derecelerine göre üç durum ortaya çıkar:
- derece[px] > derece[py]: py'yi px'in altına bağlayın — px'in derecesi değişmez
- derece[px] < derece[py]: px'i py'nin altına bağlayın — py'nin derecesi değişmez
- derece[px] == derece[py]: py'yi px'in altına bağlayın (veya tersini yapın) — yeni kökün derecesi 1 artar
Derece yalnızca dereceler eşit olduğunda artırılır. Bu, derece n için en az 2^n düğüm gerektiği anlamına gelir; dolayısıyla en büyük derece O(log n) olur. Bu özellik, yol sıkıştırması olmadan bile find yollarını kısa tutar.
# 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))Birleştirilmiş Yol Sıkıştırması + Dereceye Göre Birleştirme
Hem yol sıkıştırması hem de dereceye göre birleştirme birlikte kullanıldığında işlem başına amortize edilmiş süre O(alpha(n)) değerine, yani ters Ackermann fonksiyonuna, düşer. Her pratik girdi boyutu için (2^65536 değerine kadar) alpha(n) en fazla 4'tür. Bu, fiilen sabit zamandır.
Yol sıkıştırması dolaşmalardan sonra ağaçları aşağıdan yukarıya düzleştirirken, dereceye göre birleştirme birleştirmeler sırasında ağaçların yukarıdan aşağıya uzunlaşmasını önler. Birlikte birbirlerini tamamlarlar: Derece başlangıç derinliğini sınırlar, sıkıştırma ise ilk dolaşmadan sonra bu derinliği ortadan kaldırır.
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 smallTers Ackermann Fonksiyonunu Anlamak
Ackermann fonksiyonu A(m, n), herhangi bir ilkel özyinelemeli fonksiyondan daha hızlı olmak üzere olağanüstü hızlı büyür. Bunun tersi olan alpha(n), A(m, m) >= n koşulunu sağlayan en küçük m olarak tanımlanır. Ackermann fonksiyonu çok hızlı büyüdüğü için alpha(n) akıl almaz derecede yavaş büyür.
n = 10^80 olduğunda (gözlemlenebilir evrendeki atomların sayısı), alpha(n) yine yalnızca 4'tür. Bu nedenle her iki iyileştirmeye sahip DSU, tüm pratik ortamlarda fiilen sabit zamanlı kabul edilir. alpha(n) değerinin 5'i aşacağı kadar büyük gerçek bir problemle hiçbir zaman karşılaşmazsınız.
# 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.')Derece mi Boyut mu: Hangisi Kullanılmalı
Dereceye göre birleştirmeye alternatif olarak boyuta göre birleştirme kullanılabilir: Küçük boyutlu ağacı her zaman büyük boyutlu ağacın altına bağlayın. Her iki yaklaşım da ağaç yüksekliği için O(log n) güvencesi sağlar. Boyutlar kesin sayımlar olduğu için boyuta göre birleştirmeyi anlamak çoğu zaman daha kolaydır; dereceler ise sıkıştırmadan sonra gerçek yüksekliği yansıtmayabilecek üst sınırlardır.
Mülakatlarda iki yaklaşım da kabul edilebilir. Boyuta göre birleştirmenin ek avantajı, birçok problemin gerektirdiği bileşen boyutlarını ek bir maliyet olmadan sağlamasıdır. Dereceye göre birleştirme kuramsal açıdan biraz daha zariftir ve ters Ackermann sınırına ilişkin Tarjan'ın özgün ispatıyla örtüşür.
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)])İspat Taslağı: Derece Neden O(log n) Olarak Kalır
Derecesi r olan bir DSU ağacının en az 2^r düğüm içerdiğini tümevarımla kanıtlayabiliriz. Temel durum: Derece 0, tek bir düğüm anlamına gelir (2^0 = 1). Tümevarım adımı: Derece r yalnızca derece r-1 olan iki eşit ağacın birleşmesiyle artar. Tümevarım varsayımına göre her alt ağaçta en az 2^(r-1) düğüm bulunur; dolayısıyla birleşen ağaçta en az 2 × 2^(r-1) = 2^r düğüm vardır.
Derecesi r olan bir ağaçta en az 2^r düğüm bulunduğuna ve toplam n düğümümüz olduğuna göre, en büyük derece en fazla log₂(n) olur. Bu, yol sıkıştırması olmadan find işleminin O(log n) sürede çalıştığı, yol sıkıştırmasıyla ise amortize edilmiş maliyetin çok daha fazla düştüğü anlamına gelir.
# 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}')Yarışmalı Programlama için DSU Şablonu
Yarışmalı programlama ve mülakatlarda kısa, doğru ve tüm uç durumları yöneten, sahada sınanmış bir DSU şablonu istersiniz. Aşağıdaki şablon, yolun yarıya indirilmesini (tek geçişli sıkıştırma) boyuta göre birleştirmeyle birleştirir; bu kombinasyon hızlı yazmak için kolaydır ve özyinelemeyi tamamen önler.
Her zaman parent[i] = i ve size[i] = 1 atamalarını yapın. find işleminden sonra kökün size değerinin tüm bileşeni yansıttığını unutmayın. size[x] değerini doğrudan hiçbir zaman kullanmayın; her zaman size[find(x)] çağrısını yapın.
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)) # 3DSU Ne Zaman Yeterli Değildir
DSU kümeleri birleştirmeyi destekler, ancak bir kümeyi yeniden iki kümeye bölmeyi desteklemez. Bir problem hem grupları birleştirmeyi hem de ayırmayı gerektiriyorsa farklı bir veri yapısına (örneğin bir bağlantı-kesme ağacına) ihtiyacınız vardır. DSU ayrıca her grubun öğelerini yerel olarak saklamaz; bunun için ek bir komşuluk listesi veya sözlük gerekir.
Ayrıca standart DSU, değişiklik yapılmadan ağırlıklı kenarları desteklemez (ağırlıklı DSU daha gelişmiş bir çeşittir). Bağlantılı düğümler arasındaki en ucuz yol gibi problemler için Dijkstra veya BFS daha uygundur. DSU'nun kapsamını tanımak, onu yanlış yerde kullanmanızı önler.
# 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] = pxBağlantılılık için DSU ile BFS/DFS karşılaştırması
Hem BFS/DFS hem de DSU statik bağlantılılık sorgularını çözer, ancak güçlü oldukları yönler farklıdır. BFS/DFS O(V + E) zamanında çalışır ve düğümler arasındaki gerçek yolu bulabilir. DSU, giderek büyüyen kenar kümeleri üzerinde çok sayıda bağlantılılık sorgusunu sorgu başına neredeyse O(1) maliyetle yanıtlar — kenarların birer birer geldiği çevrim içi algoritmalar için idealdir.
Tüm kenarları baştan alıyor ve yalnızca bağlantılılığa ihtiyaç duyuyorsanız ikisi de işe yarar. Kenarlar dinamik olarak geliyor ve her yeni kenardan sonra bağlantılılık sorgularını yanıtlamanız gerekiyorsa DSU açıkça daha iyi seçimdir. Kısa yola da ihtiyaç duyan problemlerde BFS kullanmalısınız.
# 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.')DSU ile Minimum Örten Ağaç Alıştırması
Minimum örten ağaç için Kruskal algoritması doğrudan DSU kullanır. Tüm kenarları ağırlıklarına göre sort edin, ardından uç noktaları farklı bileşenlerdeyse her kenarı açgözlü biçimde ekleyin (döngü oluşmaz). DSU, döngü denetimini neredeyse O(1) maliyetle sağlar. Sonuç, n-1 kenarlı bir MST'dir.
Bu, DSU'nun gücünün klasik bir gösterimidir: saf döngü denetimini O(E × V) maliyetinden O(E × alpha(n)) sürecine dönüştürür. E log E sıralamasıyla Kruskal'ın toplam süresi O(E log E) olur ve DSU işlemleri sort işlemine kıyasla o kadar hızlıdır ki ihmal edilebilir.
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)rollback'li DSU: Çevrim Dışı Bağlantılılık
Standart DSU, geri alma işlemlerini desteklemez. Ancak rollback'li DSU (tarihçeli DSU olarak da adlandırılır) bunu destekler: geri alınması zor olan yol sıkıştırması yerine yalnızca dereceye göre union kullanın ve her union işlemini bir yığına kaydedin. Geri almak için yığından pop edin ve ebeveyn ile dereceyi geri yükleyin. Bu yaklaşım, kenarların eklenip çıkarılabildiği çevrim dışı dinamik bağlantılılık problemlerinin çözülmesini sağlar.
Standart mülakatlarda nadiren görülen ileri düzey bir varyant olsa da bu yaklaşım, kritik değişmezin yol sıkıştırması değil, dereceye göre union olduğunu gösterir. Yol sıkıştırması olmadan her find işlemi O(log n) sürer; rollback ile yığın işlemleri O(1) olduğundan toplamda işlem başına O(log n) elde edilir ve O(alpha(n)) yerine bu maliyet ortaya çıkar.
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)) # FalseHızlı Kontrol
Bu dersteki Veri Yapıları & Algoritmalar — Kodlama Mülakatına Hazırlık kavramlarını anlayışınızı sınayın.
Ders Özeti
Bu derste şunları öğrendiniz: dereceye göre union her zaman daha sığ ağacı daha derin ağacın altına bağlar, derece yalnızca eşit dereceli iki ağaç birleştiğinde artar ve ağaç yüksekliğini O(log n) düzeyinde tutar ve yol sıkıştırmayı dereceye göre union ile birleştirmek O(alpha(n)) amortize maliyet sağlar — pratikte sabit zaman. Sırada, grafiklerde gereksiz bağlantı ve döngü tespiti için tam optimal DSU'yu uygulayacağız.
Sıkça Sorulan Sorular
“Dereceye Göre Birleştirme ve Ters Ackermann Sınırı” dersi ücretsiz mi?
Evet — “Dereceye Göre Birleştirme ve Ters Ackermann Sınırı” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.
“Dereceye Göre Birleştirme ve Ters Ackermann Sınırı” dersinde ne öğreneceğim?
Ağaçları sığ tutmak için dereceye dayalı birleştirme ekleyin ve birleşik optimizasyonların neden amorti edilmiş O(alpha(n)) — fiilen sabit — süre verdiğini anlayın. Coding Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 2. dersidir.
“Dereceye Göre Birleştirme ve Ters Ackermann Sınırı” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Coding Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- Yol Sıkıştırmalı DSU
- Dereceye Göre Birleştirme ve Ters Ackermann Sınırı
- Gereksiz Bağlantı ve Çevrim Belirleme
- Hesapları Birleştirme ve Bağlantılı Bileşenler