Effizienz von Algorithmen SS09

Aus ProgrammingWiki
< AuK
Archivierte Version vom 2010-03-22T11:40:42+00:00. Aktuelle Version

Inhaltsverzeichnis

Effizienzbegriff

Ein Algorithmus heißt effizient, wenn er ein vorgegebenes Problem mit möglichst geringem Ressourcenaufwand (Zeit, Speicher) löst.

Diese Formulierung muss weiter präzisiert werden. Außerdem ist zu beachten, dass Zeit und Speicher ineinander "umwandelbar" sind, d.h. wenn man bei der Modellierung knappen Speicher wählt, kann es sein, dass der Algorithmus Zusatzaufwand betreiben muss, da gewisse Daten zwischengerechnet werden müssen und eben nicht direkt zur Verfügung stehen.

Beispiel: Dublettensuche in einer Liste

Vereinfachend nehmen wir an, dass es sich um Listen mit Zufallszahlen handelt. Sobald ein doppeltes Listenelement gefunden wurde, soll das Verfahren mit der Ausgabe dieses Elements stoppen, anderenfalls stoppt der Algorithmus ohne Ausgabe eines Wertes.

Das Programm aus dem ersten Lösungsvorschlag arbeitet mit quadratischem Aufwand:

Die folgende Prozedur stellt eine Liste mit n=30 Zufallszahlen aus dem Intervall [0,m[ bereit, m=100.

<eval id="4ba10f230009b">(zliste 30 100)</eval>

Die Dublettensuche wird durch zwei verschachtelte Laufanweisungen berechnet. Die darin enthaltene Variable escape sorgt dafür, dass der Zyklus verlassen wird, sobald eine Dublette gefunden wurde.

<eval id="4ba11bad8f665"> (let* ((n 20)(a (list-&gt;vector (zliste (+ n 1) 300)))(escape #f) (vergleiche 0))</eval>

 (display a)(newline)
 (do ((i 1 (+ i 1)))
   ((or escape (= i n)) vergleiche)
   (do ((j (+ i 1) (+ j 1)))
     ((or escape (> j n)) 'stop)
     (set! vergleiche (+ vergleiche 1))
     (if (= (vector-ref a i) (vector-ref a j))
         (begin
           (set! escape #t)
           (display (vector-ref a i))
           (newline))))))

Die Anzahl der Vergleiche beträgt höchstens (n-1)+(n-2)+...+1=\frac{n(n-1)}{2}. Für n=20 sind das also höchstens 190 Vergleiche. Die Dublettenermittlung erfolgt also mit quadratischem Aufwand.

Eine aus dem Hashing bekannte Idee liefert ein wesentlich schnelleres Dublettsuchverfahren. Es braucht allerdings auch viel mehr Speicher. Das ist keine Seltenheit: Gibt man mehr Speicher, kann der darüber organisierte Prozess Rechenzeit einsparen. Umgekehrt haben Speichersparmaßnahmen negative Auswirkungen auf die Performance.

Die Idee besteht darin, für jedes Element A[i] des Zufallsvektors in einem zweiten Vektor B[A[i]] dessen Existenz zu vermerken. Der Wert des Elements ist also der betreffende Index von B. Vektor B wird mit false initialisiert, was so viel bedeutet, wie das das betrachtete Element beim Durchlaufen des Vektors noch nicht vorkam. Für jedes Element wird true in B[A[i]] vermerkt, wenn der vorherige Wert false war. Ist der ursprüngliche Wert jedoch true, so ist klar, dass der betrachtete Wert schon vorhanden ist, d.h. eine Dublette wurde gefunden.

Die Bestimmung des Maximums der in der Liste zusammengefassten Zufallszahlen kann bei der Listenbildung erledigt werden und wird deshalb aufwandsmäßig nicht zusätzlich veranschlagt.

<eval id="4ba12503dc1ea"> (let* ((n 20)(a-list (zliste (+ n 1) 300))(a (list-&gt;vector a-list))</eval>

      (b (make-vector (+ 1 (apply max a-list)) #f))(escape #f)(vergleiche 0))
 (display a)(newline)
 (do ((i 1 (+ i 1)))
   ((or escape (= i n)) vergleiche)
   (set! vergleiche (+ vergleiche 1))
   (if (vector-ref b (vector-ref a i))
       (begin 
         (set! escape #t)
         (display (vector-ref a i))(newline))
       (vector-set! b (vector-ref a i) #t))))

Es finden maximal n-1, bei n=20 also 19 Vergleiche statt.

Polynomialer vs. exponentieller Aufwand

Polynomialer Aufwand:

T(n)=a_r n^r + a_{r-1} n^{r-1} + \ldots + a_1 n^1 + a_0~, \mbox{mit } r\in\mathbb{N}_0,~a_r,\ldots, a_0\in\mathbb{R}_0^+,~a_r\neq 0.

Hierzu zählen auch die Aufwandsfunktionen, die sich mit Logarithmen der folgenden Form beschreiben lassen. Man spricht von quasipolynomialen Aufwänden.

T(n)=a\log_c(n)

Exponentieller Aufwand: T(n)=c\cdot z^n~, wobei z,~c\in\mathbb{R},~c\neq0\mbox{ und } z>1.

Auch die Fakultätsfunktion beschreibt einen exponentiellen Zusammenhang, wie die Stirlingsche Formel zeigt:

n!\approx \sqrt(2\pi n)\left(\frac{n}{e}\right)^n.

Aufgrund des gegebenen Definitionsbereiches bestehen die Graphen der Funktionen eigentlich aus Punkten. Zur besseren Visualisierung werden sie jedoch als geschlossene Linienzüge dargestellt.


Vergleich verschiedener polynomialer und pseudopolynomialer Aufwände

gnuplot Bilder einfügen, s. Bild 2.1 (S. 31)

Asymptotische Aufwandsordnungen