$\O(N^3)$.
\proof
-Definujme $H$~jako maximální vý¹ku vrcholù s~pøebytkem.
- $$H:=\max\{h(v);v \not= z,s, f^\triangle (v)\geq 0\}$$
+Definujme $H$~jako maximální vý¹ku vrcholù s~pøebytkem:
+ $$H:=\max\{h(v) : v \not= z,s, f^\triangle (v)\geq 0\}.$$
Bìh algoritmu $G'$ rozdìlíme na fáze tak, ¾e fáze skonèí po ka¾dé zmìnì
$H$. Odhadneme poèet nenasycených pøevedení v~jedné fázi: bude jich
-nanejvý¹ stejnì, jako vrcholù, které se na zaèátku fáze nacházely na
-nejvy¹¹í hladinì -- z~jiných vrcholù v~prùbìhu fáze nic nepøevádíme,
+nanejvý¹ stejnì jako vrcholù, které se na zaèátku fáze nacházely na
+nejvy¹¹í hladinì -- z~jiných vrcholù v~prùbìhu fáze nic nepøevádíme
a~nenasycené pøevedení mù¾eme provést z~ka¾dého vrcholu nejvý¹e
jednou. Poèet nenasycených pøevedení za fázi je $\leq N$.
nebo zvý¹ením~$H$ a~odhadneme jejich poèty. Maximálnì $2N^2$ fází mù¾e
konèit zvý¹ením~$H$, proto¾e dle lemmatu Z~provedeme nanejvý¹ $2N^2$
zvednutí. Sní¾ením~$H$ mù¾e konèit nanejvý¹ $2N^2$ fází, proto¾e~$H$
-klesne v¾dy alespoò o~1, pùvodnì bylo 0 a~nikdy nemù¾e být záporné --
+klesne v¾dy alespoò o~jedna, pùvodnì bylo nula a~nikdy nemù¾e být záporné --
klesnout tedy nemù¾e víckrát ne¾ vzrùst.
Máme maximálnì $4N^2$ fází o~nejvý¹e~$N$ nenasycených pøevedení,
Nyní budeme zkoumat poèty pøevedení v~obou typech fází.
Jak víme z~minulého lemmatu, v¹ech fází je nanejvý¹ $4N^2$, tak¾e
v~laciných se provede nanejvý¹ $N^2K$ nenasycených pøevedení.
-Za úèelem zkoumání drahých fází definujeme potenciál
+Za úèelem zkoumání drahých fází definujeme potenciál:
$$\psi:=\sum_{v\not=z,s; f^\triangle(x)>0}{ p(v)\over K},$$ kde
$p(v):= \vert\{u : h(u) \leq h(v)\}\vert$, èili poèet vrcholù ve stejné
nebo men¹í vý¹ce ne¾~$v$. Víme, ¾e na zaèátku bude $\psi \leq
Zvednutím vrcholu~$v$ se hodnota $p(v)$ zvý¹í maximálnì o~$N$, u~libovolného
jiného vrcholu~$w$ $p(w)$ klesne nebo se nezmìní, potenciál tedy
-vzroste maximálnì o~$N/K$. Pøedchozích èástí
+vzroste maximálnì o~$N/K$. %Pøedchozích èástí
Pøi sytém pøevedení po hranì z~$u$ do~$v$ (z~minula víme, ¾e se v¾dy
-provádí po hranì spádu nejvý¹e 1) se mohl potenciál zmen¹it o~$p(u)/K$
+provádí po hranì spádu nejvý¹e jedna) se mohl potenciál zmen¹it o~$p(u)/K$
a~mohl se zvìt¹it o~$p(v)/K$. Zvìt¹í se tedy nanejvý¹ o~$N/K$
Pøi nenasyceném pøevedení z~potenciálu urèitì ubyde o~$p(u)/K$
a~mo¾ná pøibyde $p(v)/K$. Celkovì se tedy sní¾í nanejvý¹
o~${p(u)/K} - {p(v)/K}$, co¾ je $1/K$~poètu prvkù na nejvy¹¹í
hladinì. Z~minulého lemmatu víme, ¾e poèet nenasycených pøevedení
v~jedné fázi je men¹í nebo roven poètu vrcholù na nejvy¹¹í hladinì na
-zaèátku fáze. Vzhledem k~tomu, ¾e zkoumáme drahé fáze v~nich¾ probìhne
+zaèátku fáze. Vzhledem k~tomu, ¾e zkoumáme drahé fáze, v~nich¾ probìhne
více ne¾~$K$ nenasycených pøevedení, vrcholù na nejvy¹¹í hladinì musí
být na zaèátku fáze také více ne¾~$K$, potenciál se tedy sní¾í o~více
ne¾ ${K/K}=1$.
\medskip
\h{Tøídìní}
-\s{Definice:} Komparátorová sí» je kombinaèní obvod jeho¾ hradla jsou
+\s{Definice:} {\I Komparátorová sí»} je kombinaèní obvod, jeho¾ hradla jsou
komparátory:
\centerline{\epsfbox{sortnet.0}}
-Výstupy komparátorù se nevìtví.
+\>Výstupy komparátorù se nevìtví.
\medskip
-{\>\sl Bubble sort}
+\s{Pøíklad:} {\sl Bubble sort}
\twofigures{sortnet.1}{Bubble.1}{143pt}{sortnet.2}{Bubble.2}{143pt}
$N^2$.
\medskip
-{\>\sl Merge sort}
+\s{Pøíklad:} {\>\sl Merge sort}
\centerline{\epsfbox{sortnet.4}}
\medskip
-\s{Definice:} Øekneme, ¾e posloupnost $x_0,\dots,x_{n-1} $ je èistì bitonická,
-pokud pro nìjaké $x_j\in\{1\dots n-1\} $ platí, ¾e
-$$x_0\leq x_1\leq \dots \leq x_j \geq x_{j+1}\geq\dots \geq x_{n-1}$$
-Posloupnost je bitonická, pokud existuje $k\in \{1\dots n-1\}$, pro
+\s{Definice:} Øekneme, ¾e posloupnost $x_0,\dots,x_{n-1} $ je {\I èistì bitonická},
+pokud pro nìjaké $x_j\in\{1, \dots, n-1\} $ platí:
+$$x_0\leq x_1\leq \dots \leq x_j \geq x_{j+1}\geq\dots \geq x_{n-1}.$$
+Posloupnost je {\I bitonická}, pokud existuje $k\in \{1\dots n-1\}$, pro
které platí, ¾e posloupnost
$x_k,x_{k+1 \bmod n},\dots, x_{k+n-1 \bmod n}$ je èistì bitonická.
-\s{Definice: Separátor $S_n$}
-Je sí», ve které jsou v¾dy~$i$-tý a~$i+1$-ní (pro $i=0,\dots,
-{n/2}-1$) prvek vstupu propojeny komparátorem, minimum bude~$i$-tým,
-maximum $i+1$-ním prvkem výstupu.
+\s{Definice:} {\I Separátor $S_n$}
+je sí», ve které jsou v¾dy~$i$-tý a~$(i+{n/2})$-tý prvek vstupu
+(pro $i=0,\dots, {n/2}-1$) propojeny komparátorem, minimum bude~$i$-tým,
+maximum $(i+1)$-ním prvkem výstupu.
\figure{sortnet.3}
{$(y_i, y_{i+{n/2}}) = CMP(x_i, x_{i+{n/2}})$} {300pt}
$y_0,\dots, y_{n-1}$ je posloupnost, která splòuje:
(i) $y_0,\dots, y_{n/2 -1}$ a~$y_{n/2},\dots, y_{n-1}$ jsou
-bitonické posloupnosti.
+bitonické posloupnosti,
-(ii) Pro v¹echna $i,j< {n/2}$ platí $y_i < y_j + {n/2}$
+(ii) Pro v¹echna $i,j< {n/2}$ platí $y_i < y_{j + {n/2}}$.
\proof
-(i) Nejprve nahlédneme, ¾e Lemma platí je-li vstupem èistì bitonická
+(i) Nejprve nahlédneme, ¾e lemma platí je-li vstupem èistì bitonická
posloupnost -- najdeme nejmen¹í~$k$ takové, ¾e $x_k$ a~$x_{k+{n/2}}$
se prohodí. Pokud ho nenajdeme, separátor neudìlá vùbec nic a~obì
tvrzení lemmatu zøejmì tedy platí. Øeknìme, ¾e $x_m$ je maximum
bitoniènosti se nic nezmìní.
(ii) Plyne z~definice separátoru.
+\qed
\medskip
\centerline{\epsfbox{sortnet.7}}
\medskip
-\s{Definice: Bitonická tøídièka $B_n$}
+\s{Definice:} {\I Bitonická tøídièka $B_n$}
\centerline{\epsfbox{sortnet.5}}
Tøídièka se dá pou¾ít ke slévání, mù¾eme tak s~její pomocí sestavit
souèástky $M_n$ mergesortové sítì. Setøídìné posloupnosti
$x_0,\dots, x_{n-1}$ a~$y_0,\dots, y_{n-1}$ spojíme do jedné bitonické
-$x_0,\dots, x_{n-1},y_{n-1},\dots, y_0$. Z~takové posloupmosti pomocí
+$x_0,\dots, x_{n-1},y_{n-1},\dots, y_0$. Z~takové posloupnosti pomocí
$B_{2n}$ vytvoøíme setøídìnou posloupnost.
bude mít
${\O}(\log^2 N)$ hladin a~${\O}(N\log^2 N)$ hradel.
-Existuje tøídící algoritmus, kterému staèí ${\O}(\log N)$ hladin,
+Existuje tøídicí algoritmus, kterému staèí ${\O}(\log N)$ hladin,
ale jeho multiplikaèní konstanta je pøíli¹ veliká, tak¾e je v~praxi
nepou¾itelný.
projects / ads2.git / blobdiff