Nastrel prednasky o teorii cisel, ale zatim nejde ani prelozit.

[ads2.git] / 5-sortnet / 5-sortnet.tex

diff --git a/5-sortnet/5-sortnet.tex b/5-sortnet/5-sortnet.tex
index 7df746d2251695ec14b2cb2c2707f1cbb5db4e53..02f0cfbff752c3e4682e1ff7b5a46d251fc62552 100644 (file)
--- a/5-sortnet/5-sortnet.tex
+++ b/5-sortnet/5-sortnet.tex
@@ -87,8 +87,20 @@ p
 $\O(N^2\sqrt M)$.
 \qed
 
-%\s{Implementace:}
-%?????
+\s{Implementace:}
+Narozdíl od pùvodní verze algoritmu si ve verzi se zvedáním nejvy¹¹ího
+vrcholu nebudeme pamatovat seznam vrcholù s~kladným pøebytkem, ale
+setøídìný seznam pøihrádek. V~ka¾dé pøihrádce budou jen vrcholy
+s~pøebytkem s~urèitou vý¹kou. Vyhledání nejvy¹¹ího vrcholu tedy
+zvládneme v konstantním èase, stejnì pro zvý¹ení vrcholu nám staèí
+$\O(1)$ (buï vrchol pøesuneme do vedlej¹í pøihrádky, nebo pro nìj
+zalo¾íme novou). Pøevádíme-li pøebytek do vrcholu, kde pøedtím nebyl,
+pak musí mít vý¹ku o~$1$ ni¾¹í, ne¾ vrchol, ze kterého pøebytek
+pøevádíme (jinak by existovala nenasycená hrana se spádem dva, co¾
+nejde). Najít (pøípadnì vytvoøit) pøihrádku novì vzniklému vrcholu
+s~pøebytkem tak také stihneme v~konstantním èase.
+Pro zvednutí nám tedy stále staèí èas $\O(N)$ a libovolné
+pøevedení pøebytku zvládneme v~$\O(1)$.
 
 \medskip
 \h{Tøídìní}