From f25e3d46450bf475ecd82003fb35e34db96a76b8 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Thu, 23 Jan 2014 19:17:50 +0100 Subject: [PATCH] Dijkstra: U celociselnych delek lepe popisujeme rozsah okna --- 13-dijkstra/13-dijkstra.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/13-dijkstra/13-dijkstra.tex b/13-dijkstra/13-dijkstra.tex index 7269751..7bc32bc 100644 --- a/13-dijkstra/13-dijkstra.tex +++ b/13-dijkstra/13-dijkstra.tex @@ -318,7 +318,7 @@ vypr asymptoticky nezhor¹íme, prostor klesne na~$\O(L+m)$. Podobný trik mù¾eme pou¾ít i pro libovolnou jinou datovou strukturu: rozsah èísel -rozdìlíme na~\uv{okna} velikosti~$L$ (v~$i$-tém oknì jsou èísla $iL,\ldots,(i+1)L-1$). +rozdìlíme na~\uv{okna} velikosti~$L$ (v~$i$-tém oknì jsou èísla $iL,iL+1,\ldots,(i+1)L-1$). V~libovolné chvíli mohou tedy být neprázdná nejvý¹e dvì okna. Staèí nám proto poøídit si dvì struktury pro ukládání èísel v~rozsahu $0,\ldots,L-1$ -- jedna z~nich bude reprezentovat aktuální okno (to, v~nìm¾ le¾elo minulé minimum), -- 2.39.2