\( \newcommand{\data}{\textnormal{data}} \newcommand{\lower}{\textnormal{lower}} \newcommand{\upper}{\textnormal{upper}} \newcommand{\array}{\textnormal{array}} \newcommand{\depth}{\textnormal{depth}} \newcommand{\height}{\textnormal{height}} \newcommand{\BST}{\textnormal{BST}} \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\lognpone}{\ceil{\log_2(n+1)}} \newcommand{\bitsize}{\textnormal{bitSize}} \newcommand{\mult}{\textnormal{mult}} \newcommand{\inneighbors}{\textnormal{inNeighbors}} \newcommand{\outneighbors}{\textnormal{outNeighbors}} \newcommand{\neighbors}{\textnormal{neighbors}} \newcommand{\indeg}{\textnormal{indeg}} \newcommand{\outdeg}{\textnormal{outdeg}} \newcommand{\scc}{\textnormal{scc}} \newcommand{\R}{\mathbb{R}} \newcommand{\val}{\textnormal{val}} \newcommand{\dist}{\textnormal{dist}} \newcommand{\flows}{\textnormal{flows}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\N}{\mathbb{N}} \)

Bis jetzt haben wir bei den meisten Algorithem sehr genau auf die parallele Laufzeit geschaut; $O(\log n)$ war dabei stets unser Ziel, und $O(\log^2 n)$ hatte sich nur halbwegs gut angefühlt. So haben wir uns z.B. mit dem recht einfachen MergeSort mit $O(\log^2 n)$ Zeit nicht zufrieden gegeben und in Coles MergeSort einen (recht kompliziierten) Algorithmus mit paralleler Zeit $O(\log n)$ kennengelernt. Bei der Arbeit haben wir z.B. beim Listenpräfix versucht, ein $O(n \log n)$ zu einem $O(n)$ zu optimieren. Gleiches in : dort war ja ein Algorithmus mit $O(n \log n)$ Arbeit recht leicht zu bekommen (mit Sortieren); für $O(n)$ Arbeit mussten wir uns dagegen anstregen.

Schon im Kapitel über Graphenalgorithmen, insbesondere beim Berechnen der Determinante und von perfekten Matchings haben wir begonnen, diese Sorgfalt über Bord zu werfen und haben ohne zu Zögern Algorithmen mit $O(n^3)$ Prozessoren und Laufzeit $O(\log^2 n)$ oder sogar $O(\log^3 n)$ akzeptiert. In diesem Kapitel nun werfen wir die Sorgfalt völlig über Bord und definieren:

Effizienzbegriff. Ein paralleler Algorithmus gilt uns als effizient, wenn es ein $k \in \N$ gibt, so dass er bei Eingaben der Größe $n$ maximal $O(\log^k(n))$ Zeitschritte ausführt und $O(n^k)$ Prozessoren benötigt.

Speicherkomplexität

Wir gehen davon aus, dass auch der gesamte Speicher polynomiell groß ist; das heißt, nicht nur die Anzahl der tatsächlich verwendeten Speicherzellen, sondern der gesamte Adressbereich des Speichers ist polynomiell groß. In der Tat: falls es exponentiell viele Speicherzellen geben sollte, dann würden gewissen Zellen ja eine polynomiell lange Adresse benötigen; selbst die Adresse zu lesen würde dann polynomiell viele Zeitschritte benötigen. Im allgemeinen geht man daher im PRAM-Modell davon aus, dass es eine Wortgröße $w$ gibt, die logarithmisch in $n$ ist, und jede Adresse lässt sich als ein Wort schreiben. Falls wir größere Adressen hätten, dann wäre Prozessor schreibn $x$ in Zelle $i$ ja gar keine atomare Operation mehr.