X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=9-decomp%2F9-decomp.tex;h=03a9209f6c4fdffec9df12b44371f6484b2b9e9c;hb=5f689855aa5c0a52fb42f6e1985d8729ebf4b1fe;hp=e423487841733c11641184c78c9e1f766d194366;hpb=f97156a6be8e6803ae7cfed05c8a0259a34d9324;p=ga.git diff --git a/9-decomp/9-decomp.tex b/9-decomp/9-decomp.tex index e423487..03a9209 100644 --- a/9-decomp/9-decomp.tex +++ b/9-decomp/9-decomp.tex @@ -141,7 +141,7 @@ je p 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 $\O(\log^* n)$), -naúètujeme právì provádìné operaci. Celkem jimi tedy strávíme èas $\O(\ell\log^*n)$. +naúètujeme právì provádìné operaci. Celkem jimi tedy strávíme èas $\O(m\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ì, jeho¾ rodiè le¾í také v~$k$-té skupinì.