From 175a6044081f12de0c7c0e4d61be01e4c7da33bb Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Thu, 9 Jan 2025 10:12:59 +0100 Subject: [PATCH] =?utf8?q?M/m=20dekompozice:=20Lep=C5=A1=C3=AD=20zna=C4=8D?= =?utf8?q?en=C3=AD?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- 9-decomp/9-decomp.tex | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/9-decomp/9-decomp.tex b/9-decomp/9-decomp.tex index 4645d52..5255b9e 100644 --- a/9-decomp/9-decomp.tex +++ b/9-decomp/9-decomp.tex @@ -193,10 +193,10 @@ hrany komprimovaných cest tučně. \medskip \fig{mima.epdf}{} -\s{Algoritmus pro cesty:} Cestu délky~$l$ rozdělíme na~úseky délky $\log n$, pro něž si uložíme +\s{Algoritmus pro cesty:} Cestu délky~$\ell$ rozdělíme na~úseky délky $\log n$, pro něž si uložíme množiny již přítomných hran (po~bitech jako čísla). Pak si ještě pamatujeme zkomprimovanou cestu (hrany odpovídají úsekům a jsou přítomny právě tehdy, jsou-li přítomny všechny hrany příslušného úseku) -délky $l/\log n$ a pro ni \uv{přebarvovací} strukturu pro Union-Find. +délky $\ell/\log n$ a pro ni \uv{přebarvovací} strukturu pro Union-Find. \>$\(x,y)$ (přidání hrany $e=xy$ do~cesty): \algo @@ -212,8 +212,8 @@ délky $l/\log n$ a pro ni \uv{přebarvovací} strukturu pro Union-Find. na~které nám odpoví zkomprimovaná cesta, a~dva dotazy v~krajních částečných úsecích. \endalgo -Operace uvnitř úseků pracují v~čase $\O(1)$, operace na~zkomprimované cestě v~$\O(\log l)$ -amortizovaně, ale za~dobu života struktury je jich $\O(l/\log n)=\O(l/\log l)$, takže celkově zaberou lineární čas. +Operace uvnitř úseků pracují v~čase $\O(1)$, operace na~zkomprimované cestě v~$\O(\log \ell)$ +amortizovaně, ale za~dobu života struktury je jich $\O(\ell/\log n)\subseteq \O(\ell/\log \ell)$, takže celkově zaberou lineární čas. \s{Komprese cest:} Operace na~mikro/makro-stromech budeme následujícím způsobem převádět na~operace s~jejich cestově komprimovanými podobami a na~operace s~cestovými strukturami: -- 2.39.5