TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Übungen SS09/Beispiel 4

Bestimmen Sie die Laufzeiten der unten angegebenen Algorithmen in Abhängigkeit von $n$ in $\Theta$-Notation. Verwenden Sie hierfür einen möglichst einfachen Term.

A)

  1: a = $2^{n}$;
  2: solange a > 0 {
  3:   für b = 1,..,n {
  4:     c = c + b;
  5:   }
  6:   a = $\lfloor$a/2$\rfloor$
  7: }

B)

  1: i = 1;
  2: a = 1;
  3: wiederhole
  4:   i = i + 1;
  5:   a = a * 2;
  6: bis i $\geq$ log2 n;
  7: für j = 0,..,a {
  8:   x = x + j;
  9: }

Bestimmen Sie folgende Algorithmen so, dass sie die angegebene Laufzeit erreichen:

C) $\Theta$($n^{2}$ $\cdot$ log2 n)

  1: für l = 1,..,___ {
  2:   k = n;
  3:   wiederhole
  4:     k = ___;
  5:     m = n $\ast$ k;
  6:   bis k $\leq$ 1
  7: }

D) $\Theta$(log² n)

  1: x = ___;
  2: solange x > 1 {
  3:   y = $n^{2}$ - x;
  4:   x = ___;
  5: }

Lösung

Beispiel A

Betrachten wir jede Zeile einzeln. Die erste Zeile ergibt eine Laufzeit von 1 da diese Zeile asymptotisch nur 1 mal ausgeführt wird. In der Zeile zwei haben wir eine Schleife. Da müssen wir nachsehen wie die Abbruchbedingung ist und wo die Variable für die Abbruchbedingung verändert wird. Das haben wir in Zeile 6. In Zeile 6 wird a jeden Schleifendurchgang halbiert. Das kennen wir aus der Mathematik als Logarithmus zur Basis 2. Da wir a in der ersten Zeile auf $2^{n}$ gesetzt haben, und der Logarithmus zu Basis 2 von $2^{n}$ n ergibt, wird die Schleife n-mal durchlaufen. In der Zeile 3 haben wir wieder eine Schleife, die für sich alleine n-mal durchlaufen wird. Da wir diese Schleife aber schon in einer anderen haben die auch n-mal durchlaufen wird, werden die zwei Laufzeiten multipliziert. Das ergibt dann eine Laufzeit von $n^{2}$. Zeile 4 wird asymptotisch wieder nur 1 mal durchlaufen und 1 * $n^{2}$ ergibt $n^{2}$. Zeile 6 liegt wieder in der äußeren Schleife und wird deswegen nur n-mal durchlaufen. Um nun zur asymptotischen Gesamtlauftzeit zu kommen, schauen wir uns die größte Potenz an. Da hat eindeutig $n^{2}$ gewonnen, also ist die Laufzeit für diesen Algorithmus $\Theta$($n^{2}$).

Beispiel B

Bei Beispiel B haben wir in den ersten zwei Zeilen eine Wertezuweisung, welche jeweils die Laufzeitkosten von 1 haben. In der dritten Zeile haben wir den Beginn einer Schleife, welche bei Zeile 6 ihre Abbruchbedingung hat. In der Schleife wird die Variable i jeweils um eins erhöht, also läuft die Schleife genau log2 n mal, so wie es in der Abbruchbedingung festgelegt ist. Zeile 4 und 5 sind in dieser Schleife also laufen sie ebenfalls log2 n mal. In Zeile 7 haben wir erneut eine Schleife, die genau bis zur Größe von a läuft. Die Variable a wurde in Zeile 5 festgelegt und ist log n mal mit 2 multipliziert worden. Also 2 * 2 * 2 * 2 * 2*... und so weiter. Aus der Mathematik kennen wir dies als Potenz von 2. In unserem Fall ist 2^log2 n. Das wiederum ergibt mir aber n. Also ist die Laufzeit für die Zeilen 7 und 8 jeweils n. Nun suchen wir uns wieder die größte Komplexitätsklasse. Diese wäre n. Also ist die Gesamtlaufzeit dieses Algorithmus $\Theta$(n).

Beispiel C

Wir müssen hier eine Gesamtlaufzeit von $\Theta$(n² log2 n) herausbringen. Wie wir bei Beispiel A gesehen haben, können wir eine logarithmische Laufzeit erzeugen, indem wir immer wieder durch eine Variable dividieren. Bei der einzigen Variablen bei der wir dies können wäre k. Also wäre in Zeile 4 ein $\lfloor$k/2$\rfloor$ anzuraten. Jetzt würde uns nur mehr das n² fehlen. Aufgrund dessen das wir nur mehr ein Feld haben setzen wir einfach als obere Grenze, in Zeile 1, für die Schleife n² ein.

Beispiel D

Hier soll eine Gesamtlaufzeit von $\Theta$(log² n) herauskommen. Dies kann man am einfachsten erreichen in dem man ganz trivial einfach in Zeile 1 log² n einsetzt und in Zeile 4 einfach x - 1. Ich denke, dessen bedarf es keiner weiteren Erklärungen.