Prvni cast planarity.

[ga.git] / 10-decomp / 10-decomp.tex

diff --git a/10-decomp/10-decomp.tex b/10-decomp/10-decomp.tex
index 480112f3d7f5c09a045eb4ab8a4402efeaea0951..03d484d44c759ff3ecbcbba2206d7c989c0a28a3 100644 (file)
--- a/10-decomp/10-decomp.tex
+++ b/10-decomp/10-decomp.tex
@@ -1,6 +1,6 @@
 \input ../sgr.tex
 
 \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,
 
 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
 
 \: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}
 
 
 \h{Fredericksonova clusterizace}