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

• 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 = 2n;
 2: c = n;
 3: solange a > 0 {
 4:   für b = 1,..,c {
 5:     d= c + n;
 6:   }
 7:   c = c + 1
 8:   a = $\lfloor$a/2$\rfloor$
 9: }

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: }

• Ergänzen Sie die folgenden Algorithmen so, dass sie die angegebene Laufzeit erreichen:

C) $\Theta$(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² - x;
 4:   x = ___;
 5: }

Beispiel A

In den ersten beiden Zeilen ist jeweils eine Zuweisung, mit asymptotischer Laufzeit von 1. In Zeile 3 beginnt eine Schleife mit der oberen Grenze von a. A haben wir in der ersten Zeile auf 2ⁿ und die Schleife halbiert a bei jedem Schleifendurchgang. Das heißt die schleife hat eine Laufzeit von log a. Da a aber 2ⁿ ist und log 2ⁿ n ist, hat die äußere Schleife eine Laufzeit von n. Die innere Schleife geht am Anfang nur bis n, wenn jedoch die äußere Schleife zuende ist bis 2n. Das macht aber nix, da solche konstanten Faktoren weggelassen werden können. Also hat die innere Schleife ein Laufzeit von n². In Zeile 7 sind wir wieder in der äußeren Schleife mit einer Laufzeit von n, ebenso wie in der 8. Zeile. Die Gesamtlaufzeit ist in diesem Beispiel $\Theta$(n²).

Beispiel B

Zeile 1 und Zeile 2 haben die ein asymptotisches Laufzeitverhalten von 1. In Zeile 3 beginnt eine Schleife. Die Abbruchbedingung für diese Schleife ist wenn i größer oder gleich log₂ von n ist. Da innerhalb der Schleife immer i + 1 gerechnet wird, ist die Laufzeit gleich log₂ von n. In der nächsten Schleife, Zeile 7, wird dieselbe Variable, i, genommen. Diese hat noch immer den Wert von log₂ n, also läuft auch die zweite Schleife log₂ n mal. Die Gesamtlaufzeit ist daher $\Theta$(log₂ n).

Beispiel C

In diesem Beispiel sollen wir eine Laufzeit von $\Theta$(n²) erzeugen. Wir sehen mal gleich das in Zeile 2 jeden Schleifendurchgang die Schleifenvariable von der Schleife in Zeile 3 auf n gesetzt wird. Wenn wir jetzt diese immer n-mal laufen lassen, haben wir schon mal n und müssen nur noch die äußere Schleife, Zeile 1, dazu bekommen ebenfalls bis n zu laufen und schon haben wir n². Die innere können wir dazu bringen n-mal zu laufen, indem wir in Zeile 4 k - 1 einsetzen. Um die äußere bis n laufen zu lassen können wir einfach in Zeile 1 n einsetzen.

Natürlich kann man auch so blöde/triviale Lösungen verwenden wie in Zeile 1 einfach n² einzusetzen und in Zeile 4 k/k bzw k/n. Aber ich denke nicht, dass dies Sinn der Übung ist.

Beispiel D

Gefordert ist hier eine Laufzeit von $\Theta$(log n). Wie wir schon durch andere Beispiele wissen kann man Logarithmen erzeugen indem man eine Variable immer wieder durch 2 dividiert. Da bietet sich natürlich Zeile 4 an, in die wir einfach $\lfloor$x/2$\rfloor$. Damit wir nun eine Laufzeit von log n bekommen müssen wir x natürlich mit n initialisieren. Das können wir in Zeile 1 machen, also schreiben wir in Zeile 1 n.

Ebenso wäre in Zeile 1 log n und in Zeile 4 x - 1 richtig, da kann man sich das jetzt aussuchen, da beide gleich sinnvoll erscheinen.