From 4de3e77f9c20bc20a71bdd3beb2b94d70270dcc6 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 14 Dec 2009 19:57:27 +0100 Subject: [PATCH] Goldberg: Oprava preklepu. --- 3-goldberg/3-goldberg.stamp | 2 +- 3-goldberg/3-goldberg.tex | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-) diff --git a/3-goldberg/3-goldberg.stamp b/3-goldberg/3-goldberg.stamp index 4f3bed2..46333b4 100644 --- a/3-goldberg/3-goldberg.stamp +++ b/3-goldberg/3-goldberg.stamp @@ -1 +1 @@ -2009-11-01 +2009-12-14 diff --git a/3-goldberg/3-goldberg.tex b/3-goldberg/3-goldberg.tex index ce5857f..92cc877 100644 --- a/3-goldberg/3-goldberg.tex +++ b/3-goldberg/3-goldberg.tex @@ -256,7 +256,7 @@ Rozd Teï potøebujeme odhadnout, kolik nás budou stát oba typy fází. Zaènìme s~tìmi jednodu¹¹ími -- s~lacinými. Víme, ¾e~v¹ech fází je~$\O(N^2)$. Tìch laciných bude tedy urèitì také~$O(N^2)$. Nenasycených pøevedení se~bìhem jedné laciné fáze provede nejvíce~$K$. Tedy celkem se~bìhem laciných fází provede~$\O(N^2K)$ nenasycených pøevedení. Pro~poèet nenasycených pøevedení v~drahých fázích si~zaveïme nový potenciál definovaný následovnì: -$$\Phi := \sum_{\scriptstyle{v \ne z,s} \atop \scriptstyle{f^{\Delta}(v) = 0}} {p(v) \over K},$$ +$$\Phi := \sum_{\scriptstyle{v \ne z,s} \atop \scriptstyle{f^{\Delta}(v) \ne 0}} {p(v) \over K},$$ kde~$p(v)$ je poèet takových vrcholù~$u$, které nejsou vý¹e ne¾~$v$. Neboli $$p(v) = \vert \{ u \in V \mid h(u) \leq h(v) \} \vert.$$ Tedy platí, ¾e~$p(v)$ je v¾dy nezáporné a~nejvý¹e má hodnotu~$N$. Dále víme, ¾e~$\Phi$ bude v¾dy nezáporné (nebo» je to souèet nezáporných èlenù) a~nejvý¹e bude nabývat hodnoty~$N^2 \over K$. Rozmysleme si, jak nám ovlivní tento potenciál na¹e tøi operace: -- 2.39.2