projects
/
diplomarbeit.git
/ commitdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
| commitdiff |
tree
raw
|
patch
|
inline
| side by side (parent:
64778ff
)
Verwende Theta statt gross-O.
author
Florian Forster
<octo@leeloo.octo.it>
Fri, 25 Feb 2011 16:35:28 +0000
(17:35 +0100)
committer
Florian Forster
<octo@leeloo.octo.it>
Fri, 25 Feb 2011 16:35:28 +0000
(17:35 +0100)
diplomarbeit.tex
patch
|
blob
|
history
diff --git
a/diplomarbeit.tex
b/diplomarbeit.tex
index
eda81d2
..
24ae125
100644
(file)
--- a/
diplomarbeit.tex
+++ b/
diplomarbeit.tex
@@
-270,8
+270,8
@@
Widerspruch zu der Annahme, dass alle 0-1-Folgen sortiert werden.
Im Gegensatz zum Überprüfen aller möglichen Permutationen, was der
Komplexitätsklasse
Im Gegensatz zum Überprüfen aller möglichen Permutationen, was der
Komplexitätsklasse
-$\
mathcal{O}
\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ zuzuordnen ist,
-ist das Überprüfen aller 0-1-Folgen „nur“ mit dem Aufwand $\
mathcal{O}
(2^n)$
+$\
Theta
\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ zuzuordnen ist,
+ist das Überprüfen aller 0-1-Folgen „nur“ mit dem Aufwand $\
Theta
(2^n)$
verbunden. Entsprechend ist dieses Verfahren nicht \emph{effizient} -- ein
schnelleres Verfahren ist bisher allerdings nicht bekannt. Um zu überprüfen,
ob ein Komparatornetzwerk mit 16~Leitungen die Sortiereigenschaft besitzt,
verbunden. Entsprechend ist dieses Verfahren nicht \emph{effizient} -- ein
schnelleres Verfahren ist bisher allerdings nicht bekannt. Um zu überprüfen,
ob ein Komparatornetzwerk mit 16~Leitungen die Sortiereigenschaft besitzt,
@@
-458,7
+458,7
@@
$\operatorname{OET}(3)$ sortiert.
Das \emph{Odd-Even-Transpositionsort}-Netzwerk ist weder in Bezug auf die
Anzahl der Komparatoren noch in Bezug auf die Anzahl der Schichten, in denen
sich die Komparatoren anordnen lassen, effizient. Es benötigt ${\frac12 n
Das \emph{Odd-Even-Transpositionsort}-Netzwerk ist weder in Bezug auf die
Anzahl der Komparatoren noch in Bezug auf die Anzahl der Schichten, in denen
sich die Komparatoren anordnen lassen, effizient. Es benötigt ${\frac12 n
-(n-1)} = \
mathcal{O}
(n^2)$~Komparatoren, die in $n$~Schichten angeordnet sind.
+(n-1)} = \
Theta
(n^2)$~Komparatoren, die in $n$~Schichten angeordnet sind.
Die im Folgenden vorgestellten Sortiernetzwerke benötigen deutlich weniger Komparatoren,
($\Theta(n \log (n)^2)$), die in weniger Schichten,
($\Theta(\log (n)^2)$), angeordnet sind.
Die im Folgenden vorgestellten Sortiernetzwerke benötigen deutlich weniger Komparatoren,
($\Theta(n \log (n)^2)$), die in weniger Schichten,
($\Theta(\log (n)^2)$), angeordnet sind.
@@
-574,7
+574,7
@@
Statt an eine Treppe erinnert das Muster nun an einen Trichter.
Da sich die Anzahl der Leitungen in jedem Rekursionsschritt halbiert, endet
die Rekursion nach $\log(n)$~Schritten. In jedem Rekursionsschritt werden
$\frac{n}{2}$~Komparatoren eingefügt, so dass der gesamte Mischer aus
Da sich die Anzahl der Leitungen in jedem Rekursionsschritt halbiert, endet
die Rekursion nach $\log(n)$~Schritten. In jedem Rekursionsschritt werden
$\frac{n}{2}$~Komparatoren eingefügt, so dass der gesamte Mischer aus
-$\frac{1}{2} n \log(n) = \
mathcal{O}
\left(n \log(n)\right)$~Komparatoren
+$\frac{1}{2} n \log(n) = \
Theta
\left(n \log(n)\right)$~Komparatoren
besteht, die in $\log(n)$~Schichten angeordnet werden können.
\subsubsection{Das bitone Mergesort-Netzwerk}
besteht, die in $\log(n)$~Schichten angeordnet werden können.
\subsubsection{Das bitone Mergesort-Netzwerk}
@@
-746,7
+746,7
@@
in Abbildung~\ref{fig:oe-post-recursive} dargestellt.
\end{figure}
Da die Teilfolgen $U$ und $V$ in jedem Rekursionsschritt etwa halbiert werden,
\end{figure}
Da die Teilfolgen $U$ und $V$ in jedem Rekursionsschritt etwa halbiert werden,
-bricht die Rekursion nach $\
mathcal{O}
\left(\log (n) + \log (m)\right)$
+bricht die Rekursion nach $\
Theta
\left(\log (n) + \log (m)\right)$
Schritten ab. Die exakte Anzahl der benötigten Rekursionsschritte (und damit
Schichten im Mischer-Netzwerk), hängt von der längeren der beiden
Eingabefolgen ab und beträgt $1 + \lceil \log\left(\max(n, m)\right) \rceil$.
Schritten ab. Die exakte Anzahl der benötigten Rekursionsschritte (und damit
Schichten im Mischer-Netzwerk), hängt von der längeren der beiden
Eingabefolgen ab und beträgt $1 + \lceil \log\left(\max(n, m)\right) \rceil$.
@@
-764,7
+764,7
@@
Länge der Eingabefolgen, $n$ und $m$ ab:
\end{displaymath}
Leider ist es schwierig, diese allgemeine Formel in einer geschlossenen Form
anzugeben. Aus der Anzahl der Rekursionsschritte ist jedoch leicht erkennbar,
\end{displaymath}
Leider ist es schwierig, diese allgemeine Formel in einer geschlossenen Form
anzugeben. Aus der Anzahl der Rekursionsschritte ist jedoch leicht erkennbar,
-dass $K(n,m)$ in $\
mathcal{O}
(N \log (N))$ enthalten ist.
+dass $K(n,m)$ in $\
Theta
(N \log (N))$ enthalten ist.
Für den wichtigen Spezialfall, dass $n = m = 2^{t-1}$ beträgt, lässt sich die
Anzahl der Komparatoren im Vergleich zum \emph{bitonen Mischer} angeben: Der
Für den wichtigen Spezialfall, dass $n = m = 2^{t-1}$ beträgt, lässt sich die
Anzahl der Komparatoren im Vergleich zum \emph{bitonen Mischer} angeben: Der