Laufzeit Bestimmung mittels Landau Symbolic

[gamma21]

Folgende 3 Pseudo Codes habe ich analysiert, bin mir jedoch nicht ganz sicher ob meine Ergebnisse ganz richtig sind.

i <-- 1
x <-- 1
while i<n
    a<--4*i
    for j=a,....1
        x<--x+j
    i<--a/2

Mein Problem ist hier, dass mir die Zuweisung in der for Schleife nicht ganz klar ist. Im ersten Teil (in while) wird a, n-1 mal ein Wert zugewiesen. a muss allerdings immer größer 1 sein weil i ja schon bei 1 startet. Die for Schleife würde dann keinen Beitrag leisten und das Ergebnis wäre Theta(log(n)).

a<--1
b<--1
for c=1....(1/2)log_2(n)
    a<--4a
    b<---c
    a<--a/2
i<--2^(2b)
while i>1
i<--i/2

Die for Schleife läuft einfach bis zu einem konstanten n, also gilt Theta(n). i wird außerdem zu n wenn ich für b einsetzte und somit lautet das Ergebnis Theta(n*log(n)).

Das letzte Beispiel lautet:

a<--n^3
b<--1

while a>1
    b<--b+1
    c<--n
    do
        a<--b/2
        c<--(2c)/n
        b<--b/n
    while c>=n

Hier bin ich etwas ratlos. Ist das nicht eine Endlosschleife?
Ich hoffe ihr könnt meine Ergebnisse bestätigen. Danke schon mal.

 

[httpdigest]

Die for Schleife würde dann keinen Beitrag leisten und das Ergebnis wäre Theta(log(n)).

Wieso würde die for-Schleife keinen Beitrag leisten? Sie wird ja immerhin 4*i mal pro Iteration der äußeren while-Schleife ausgeführt. Und wenn wir jede Ausführung der for-Schleife und jede Iteration der äußeren while-Schleife als eine atomare Operation zählen, für die wir die Komplexität abschätzen wollen, dann kommen wir ziemlich exakt empirisch ermittelt auf:

2^(3 + ⌊log₂ n⌋) = 8 * 2^⌊log₂ n⌋ = 2^⌊log₂ n⌋ = n

also: Θ(n)

Desweiteren: Was hat das hier mit Datenbankprogrammierung zu tun?

 

[httpdigest]

Kommen wir zu deiner zweiten Funktion:

a<--1
b<--1
for c=1....(1/2)log_2(n)
    a<--4a
    b<---c
    a<--a/2
i<--2^(2b)
while i>1
i<--i/2

Die for Schleife läuft einfach bis zu einem konstanten n, also gilt Theta(n). i wird außerdem zu n wenn ich für b einsetzte und somit lautet das Ergebnis Theta(n*log(n)).

Diese Erklärung ist nicht nachvollziehbar und sie ist leider auch falsch. Zuersteinmal läuft `i` doch nicht bis zu einem konstanten `n`. `n` ist weder konstant, noch läuft die Schleife bis `n`. Die Schleife läuft bis `0.5 log₂ n`. Das alleine setzt die Komplexität der Funktion ja schon mal auf mindestens: Θ(log₂ n)

Jetzt gibt es noch die untere while-Schleife. Wenn wir hier schauen, was `i` zu diesem Zeitpunkt sein wird, schauen wir uns an, was denn `b` sein wird. `b` wird ja im letzten Schleifendurchgang der oberen while-Schleife auf `c` gesetzt. Und `c` wiederum ist der Schleifenzähler der oberen while-Schleife, welcher den Wert `0.5 log₂ n` im letzten Schleifendurchlauf haben wird.
Wenn wir das alles einsetzen und vereinfachen, kommen wir auf: 2^(2 * 0.5 log₂ n) = 2^(log₂ n) = n.
`i` ist also `n`, wenn die untere while-Schleife startet. Da `i` nun dort immer halbiert wird und die Schleife solange läuft, wie `i` > 1 ist, wird die Schleife ca. `log₂ n` Mal ausgeführt.

Die gesamte Funktion hat dann also eine Laufzeitkomplexität von: log₂ n + log₂ n = 2 log₂ n = log₂ n
Also: Θ(log₂ n)

 

[mihe7]

Und wenn wir jede Ausführung der for-Schleife und jede Iteration der äußeren while-Schleife als eine atomare Operation zählen

Darf man die innere Schleife hier als atomare Operation ansehen oder müsste man das nicht über eine geometrische Reihe zeigen?

 

[httpdigest]

Ja, mit geometrischer Reihe wäre es ein richtiger Beweis. Hatte ich ja für die erste Funktion gar nicht gemacht. Hier noch schnell nachgeholt:

i <-- 1
x <-- 1
while i<n
    a<--4*i
    for j=a,....1
        x<--x+j
    i<--a/2

Wir müssen erstmal herauskriegen, wie häufig die äußere while-Schleife überhaupt läuft. Da `i` am Ende auf `a / 2` gesetzt wird, schauen wir, was `a` denn dann sein wird: `a = 4*i`, also: `i = a/2 = (4*i)/2` = `2*i`.
Das heißt, `i` wird immer verdoppelt, und somit hat die Schleife schon mal genau `log₂ n` Iterationen.
Die innere for-Schleife läuft pro Durchlauf der äußeren while-Schleife immer `4*i` Iterationen.
Wenn wir das ganze als geometrische Reihe formulieren wollen, dann haben wir eine Summe aus `log₂ n` Iterationen der äußeren Schleife, und jedes dieser Summanden ist genau `4*2^i` (`2^i`, weil `i` ja immer verdoppelt wird).
Somit:

Θ(Σ{i=1 .. log₂ n}(4*2^i))

Das weiß ich jetzt allerdings wirklich nicht aus dem Kopf, also `sum 4*2^i, i=1 to log2(n)` in Wolfram Alpha eingegeben, und:

8(n - 1)

Das bestätigt ziemlich die empirische Vermutung.

 

[mihe7]

Das weiß ich jetzt allerdings wirklich nicht aus dem Kopf

Σ{i=1 .. k}(aq^i) = a*(q^(k+1) - 1)/(q-1)

eingesetzt: 4*(2^(log2(n)+1)-1)/(2-1) = 4*(2*2^(log2(n)) -1 ) = 8*(2^log2(n)-1)=8(n-1) -> passt

 

[httpdigest]

Top!

 

[mihe7]

Mir ging es aber eigentlich darum:

2^(3 + ⌊log₂ n⌋) = 8 * 2^⌊log₂ n⌋ = 2^⌊log₂ n⌋ = n

Woher die log2n kommen ist klar, die 3 dürften die Einzelschritte sein aber wie kommst Du hier auf die Potenz?

 

[httpdigest]

Ach so, das war tatsächlich einfach nur Ausprobieren. Ich hab den Algorithmus einfach so implementiert und einen Zähler für jede Iteration der beteiligten Schleifen eingebaut und am Ende das ganze für verschiedene `n` laufen lassen und mir die Anzahl der Operationen/Iterationen ausgeben lassen und da sah man auf einen Blick, dass das immer Zweierpotenzen waren, die mit wachsendem `n` immer langsamer steigen (alles für integer Werte).
Hätte man sicherlich für einen wirklichen Beweis nie so gemacht.

 

[mihe7]

Ach so, das war tatsächlich einfach nur Ausprobieren.

Ach soooo Und ich grüble hier vor mich hin.

 

[gamma21]

Wieso würde die for-Schleife keinen Beitrag leisten? Sie wird ja immerhin 4*i mal pro Iteration der äußeren while-Schleife ausgeführt. Und wenn wir jede Ausführung der for-Schleife und jede Iteration der äußeren while-Schleife als eine atomare Operation zählen, für die wir die Komplexität abschätzen wollen, dann kommen wir ziemlich exakt empirisch ermittelt auf:

2^(3 + ⌊log₂ n⌋) = 8 * 2^⌊log₂ n⌋ = 2^⌊log₂ n⌋ = n

also: Θ(n)

Desweiteren: Was hat das hier mit Datenbankprogrammierung zu tun?

Mir war nicht ganz klar, wieso die Schleife überhaupt ausgeführt wird wenn im 1.Schritt i=1 ist und a=4 weil ich nicht daran gedacht habe das die Schleife ja auch rückwärts laufen kann.
Wie du allerdings auf 2^(3 + log₂ n) kommst verstehe ich nicht. Die while Schleife läuft log₂(n) mal, die for Schleife läuft im ersten Schritt 4 mal, im nächsten Schritt 8 mal (insgesamt schon 12 mal), im 3.Schritt 12 mal (insgesamt 24 mal) und so weiter. Wieso also das 2^3 bzw 2^log₂?

 

[mihe7]

Siehe Kommentar #9.

 

[gamma21]

Ich hatte leider deinen (euren) letzen Beitrag nicht gesehen. Ich denke ich verstehe das Beispiel nun. Das 2.Beispiel ist mir nun auch klar.
Kannst du mir zum 3.Beispiel einen Hinweis geben? Ist a nicht immer größer 1?
P.S: Zu welchem Thema würde der Beitrag denn am besten passen?

 

[mihe7]

Ist a nicht immer größer 1?

Nö. Für n=1 ist a=n^3=1^3=1 und damit nicht größer als 1. Die Schleifenbedingung der äußeren while-loop ist somit nie erfüllt. Für 0 <= n < 2 werden nur zwei Zuweisungen und ein Vergleich, insgesamt also 3 Schritte ausgeführt.

Für n > 1 gilt a > 1. Folglich wird die while-loop wenigstens einmal ausgeführt.

n=2 führt, wenn ich mich nicht arg vertan habe, zu einer Endlosschleife. Der Grund ist aber nicht a sondern c: c wird vor der do-loop auf n gesetzt. In der Schleife wird c <-- 2c/n berechnet. In der ersten Iteration führt dies immer zu c=2 (2*n/n=2). Da aber auch n = 2 gilt, wird sich daran in keiner Iteration etwas ändern. Folglich wird die do-loop nie verlassen.

Für n>2 funktioniert der Spaß wieder. Tatsächlich wird die do-loop aber nur einmal ausgeführt, denn für c wird in der ersten Iteration immer 2 berechnet und 2 ist nun einmal kleiner als n. Die äußere while-loop wird auch nur einmal ausgeführt, denn nach der ersten Iteration gilt immer a = 1. Es werden also immer 10 Schritte ausgeführt.

D. h. der Algorithmus terminiert nur für alle 0 <= n < 2 und für alle n > 2. Dann gilt Θ(1).

Nachtrag:

P.S: Zu welchem Thema würde der Beitrag denn am besten passen?

Gute Frage. Mit Java hat das alles nichts zu tun. Am ehesten würden IMO noch Softwareentwicklung oder Mathematik passen.