X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;ds=sidebyside;f=10-decomp%2F10-decomp.tex;h=03d484d44c759ff3ecbcbba2206d7c989c0a28a3;hb=b959c38583c5f82ef4040444f2800f7726ebedf2;hp=480112f3d7f5c09a045eb4ab8a4402efeaea0951;hpb=053fd5d167550549bea80a8d50418d7cf424e205;p=ga.git

diff --git a/10-decomp/10-decomp.tex b/10-decomp/10-decomp.tex
index 480112f..03d484d 100644
--- a/10-decomp/10-decomp.tex
+++ b/10-decomp/10-decomp.tex
@@ -1,6 +1,6 @@
 \input ../sgr.tex
 
-\prednaska{10}{Dekompozice stromù}{zapsal Ale¹ ©nupárek}
+\prednaska{10}{Dekompozice stromù}{}
 
 V~této kapitole uká¾eme nìkolik datových struktur zalo¾ených
 na~my¹lence dekompozice problému na~dostateènì malé podproblémy,
@@ -158,10 +158,14 @@ zda je p
 \:Odpovíme podle struktury pro makrostrom.
 \endalgo
 
-\s{Analýza:} Operace s~mikrostromy, spojovacími hranami a cestami jsou, jak u¾ víme,
-amortizovanì konstantní. Operace s~makrostromy také, jeliko¾ trvají $\O(\log n)$,
-ale provede se jich pouze $\O(n/\log n)$. Ka¾dou operaci \<Union> nebo \<Find>
-rozlo¾íme $\O(1)$ tìchto dílèích operací, tak¾e bude také trvat $\O(1)$ amortizovanì.
+\s{Analýza:} Operace \<Find> trvá konstantní èas, proto¾e se rozlo¾í na~$\O(1)$ \<Find>ù
+v~dílèích strukturách a ka¾dý z~nich trvá konstantnì dlouho. V¹ech $n$ operací \<Union>
+trvá $\O(n)$, jeliko¾ zpùsobí $\O(n)$ amortizovanì konstantních operací s~mikrostromy, spojovacími
+hranami a cestami a $\O(n/\log n)$ operací s~makrostromy, které trvají $\O(\log n)$ amortizovanì
+ka¾dá.%
+\foot{To je v~prùmìru $\O(1)$ na~operaci a dokonce i amortizovanì, pokud necháme inicializaci
+struktury, která je lineární, naspoøit potenciál $\O(n)$, ze~kterého budeme prùbì¾nì platit
+sluèování v~makrostromu.}
 
 \h{Fredericksonova clusterizace}