From ce059c091ac2a93ea96e4735cb467d7b16715878 Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Tue, 6 Mar 2007 19:09:32 +0100
Subject: [PATCH] Alespon hruby odhad na Union-Find.

---
 9-decomp/9-decomp.tex | 41 ++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 40 insertions(+), 1 deletion(-)

diff --git a/9-decomp/9-decomp.tex b/9-decomp/9-decomp.tex
index 43e7511..29eda2f 100644
--- a/9-decomp/9-decomp.tex
+++ b/9-decomp/9-decomp.tex
@@ -51,7 +51,7 @@ rovnou pod ko
 \s{Pozorování:} Samotné pravidlo Union by rank zajistí, ¾e strom ranku $r$ bude
 mít hloubku nejvý¹e $r$ a minimálnì $2^r$ vrcholù, tak¾e èasová slo¾itost operací
 bude omezena $\O(\log n)$ v~nejhor¹ím pøípadì.%
-\foot{Mimochodem, Path compression samotná by také na~slo¾itost $\O(\log n)$ amortizovanì staèila.}
+\foot{Mimochodem, Path compression samotná by také na~slo¾itost $\O(\log n)$ amortizovanì staèila. \cite{tarjan84setunion}}
 
 Amortizovanì se ale popsaná struktura chová daleko lépe:
 
@@ -60,6 +60,45 @@ slo
 \foot{Existuje varianta tohoto algoritmu, která dosahuje stejné slo¾itosti i v~nejhor¹ím
 pøípadì; té¾ je známo, ¾e asymptoticky lep¹í slo¾itosti nelze dosáhnout.}
 
+Dùkaz této vìty neuvádíme, jeliko¾ je technicky dosti nároèný, ale naznaèíme alespoò,
+¾e amortizovaná èasová slo¾itost je omezena iterovaným logaritmem, konkrétnì ¾e
+ve~struktuøe s~$n$ prvky trvá provedení $\ell$~operací Union a Find $\O((n+\ell)\cdot\log^* n)$.
+
+\def\up{\mathop{\uparrow}}
+
+\s{Definice:} {\I Vì¾ovou funkci} $2\up k$ definujeme následovnì: $2\up 0=1$,
+$2\up (k+1)=2^{2\up k}$.
+
+Funkce $2\up k$ je tedy $k$-krát iterovaná mocnina dvojky a $\log^*$ je funkce
+k~této funkci inverzní.
+
+Vrcholy ve~struktuøe si nyní rozdìlíme podle jejich rankù (vrchol, který ji¾ není
+koøenem, si pamatuje svùj poslední rank z~doby, kdy je¹tì koøenem byl):
+$k$-tá skupina bude tvoøena tìmi vrcholy, jejich¾ rank je od~$2\up (k-1)+1$ do~$2\up k$. Vrcholy jsou
+tedy rozdìleny do~$1+\log^*\log n$ skupin. Odhadnìme nyní shora poèet vrcholù v~$k$-té
+skupinì, vyu¾ívajíce toho, ¾e vrcholù s~rankem~$r$ je nejvý¹e~$n/2^r$:
+$$
+{n \over 2^{2\up(k-1)+1}} + {n \over 2^{2\up(k-1)+2}} + \cdots + {n \over 2^{2\up k}} \le
+{n \over 2^{2\up(k-1)}} \cdot \sum_{i=1}^\infty {1 \over 2^i} =
+{n \over 2^{2\up(k-1)}} \cdot 1 =
+{n \over 2\up k}.
+$$
+
+Operace Union a Find potøebují nekonstantní èas pouze na~vystoupání ze~zadaného vrcholu~$v$ do~koøene stromu
+a tento èas je pøímo úmìrný poètu hran na~cestì z~$v$ do~koøene. Tato cesta je následnì rozpojena a v¹echny
+vrcholy le¾ící na~ní jsou pøepojeny pøímo pod~koøen stromu. Hrany cesty, které spojují vrcholy z~rùzných
+skupin (takových je jistì $\O(\log^* n)$), naúètujeme právì provádìné operaci, tak¾e
+jimi celkem strávíme èas $\O(\ell\log^*n)$. Zbylé hrany budeme poèítat pøes celou dobu bìhu
+algoritmu a úètovat je vrcholùm.
+
+Uva¾me vrchol~$v$ v~$k$-té skupinì, který ji¾ není koøenem stromu. Hrana z~$v$ do~jeho rodièe
+bude úètována vrcholu~$v$ pouze tehdy, le¾í-li rodiè také v~$k$-té skupinì. Jen¾e
+ranky vrcholù na~cestì z~libovolného vrcholu do~koøene ostøe rostou, tak¾e pøi ka¾dém pøepojení
+rank rodièe vrcholu~$v$ vzroste, a~proto po~$2\up k$ pøepojeních bude rodiè vrcholu~$v$ v~$(k+1)$-ní
+nebo vy¹¹í skupinì. Ka¾dému vrcholu v~$k$-té skupinì tedy úètujeme nejvý¹e $2\up k$ pøepojení
+a jeliko¾, jak u¾ víme, jeho skupina obsahuje nejvý¹e $n/(2\up k)$ vrcholù, naúètujeme
+celé skupinì èas $\O(n)$ a v¹em skupinám dohromady $\O(n\log^* n)$.
+
 \h{Union-Find s~pøedem známými Uniony}
 
 Dále nás bude zajímat speciální varianta Union-Find problému, v~ní¾ dopøedu známe
-- 
2.39.2