From 5dcb00377408b9105a5ba3fdc8e6f915c3933c48 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Fri, 12 Jan 2007 21:54:53 +0100 Subject: [PATCH] Opravena amortizovana analyza mikro-/makro-dekompozice. --- 10-decomp/10-decomp.tex | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-) diff --git a/10-decomp/10-decomp.tex b/10-decomp/10-decomp.tex index 7d63783..b633a7e 100644 --- a/10-decomp/10-decomp.tex +++ b/10-decomp/10-decomp.tex @@ -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 \ nebo \ -rozlo¾íme na~$\O(1)$ tìchto dílèích operací, tak¾e bude také trvat $\O(1)$ amortizovanì. +\s{Analýza:} Operace \ trvá konstantní èas, proto¾e se rozlo¾í na~$\O(1)$ \ù +v~dílèích strukturách a ka¾dý z~nich trvá konstantnì dlouho. V¹ech $n$ operací \ +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} -- 2.39.2