Opraven popis slozitosti Kruskalova algoritmu.

[ads1.git] / 12-kostry / 12-kostry.tex

diff --git a/12-kostry/12-kostry.tex b/12-kostry/12-kostry.tex
index 064f12f0c5000bcc0257c71dbb0d550611db6d22..bf0f016a3c5fa424fdc940089be3b4049ac455b6 100644 (file)
--- a/12-kostry/12-kostry.tex
+++ b/12-kostry/12-kostry.tex
@@ -149,7 +149,7 @@ o~kter
 
 \s{Jednoduchá struktura pro komponenty:}
 Budeme pamatovat v~poli èísla komponent, ve~kterých le¾í jednotlivé vrcholy. \<Find> zvládneme v~èase $\O(1)$,
-ale \<Union> bude stát $\O(n)$. Celý algoritmus pak pobì¾í v~èase $\O(m\log n+ m + n^2) = \O(n^2)$.
+ale \<Union> bude stát $\O(n)$. Celý algoritmus pak pobì¾í v~èase $\O(m\log n+ m + n^2) = \O(m\log n+n^2)$.
 
 \s{Chytøej¹í struktura:} Ka¾dou komponentou si ulo¾íme jako strom orientovaný smìrem ke koøeni
 -- ka¾dý vrchol si pamatuje svého otce, navíc ka¾dý koøen si pamatuje velikost komponenty.