Laufzeit Bestimmung mittels Landau Symbolic

gamma21

Mitglied
Folgende 3 Pseudo Codes habe ich analysiert, bin mir jedoch nicht ganz sicher ob meine Ergebnisse ganz richtig sind.
Code:
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)).
Code:
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:
Code:
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

Top Contributor
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

Top Contributor
Kommen wir zu deiner zweiten Funktion:
Code:
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)
 

httpdigest

Top Contributor
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:
Code:
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.
 

httpdigest

Top Contributor
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.
 

gamma21

Mitglied
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₂?
 

gamma21

Mitglied
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

Top Contributor
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.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
G Laufzeit eines Algorithmus mittels Big Theta bestimmen Datenbankprogrammierung 5
T importierte Derby DB währen der Laufzeit einlesen Datenbankprogrammierung 2
S persistence.xml zur Laufzeit manipulieren Datenbankprogrammierung 0
M JPA coloumnDefinition zur Laufzeit ändern Datenbankprogrammierung 6
Psypsy Dynamisch zur Laufzeit Datenbank erzeugen Datenbankprogrammierung 2
C Hybernate DB zur Laufzeit wechseln Datenbankprogrammierung 4
Gossi Datenbank zur laufzeit wechseln... Datenbankprogrammierung 2
Y Hibernate - externe Datenbank zur Laufzeit ansprechen Datenbankprogrammierung 5
M mySQL zugriff funktionert nach ca4 stündiger laufzeit nicht Datenbankprogrammierung 6
Zrebna Wie mittels Hibernate eine Join-Tabelle als eigene Java-Klasse erstellen? Datenbankprogrammierung 5
Zrebna Wie mittels PL/SQL eine Datenbankverbindung blockieren? Datenbankprogrammierung 6
Zrebna Lediglich interne DB-Verbindungen (Connections) auslesen - mittels Java Datenbankprogrammierung 4
H MariaDB-Zugriff mittels Java SE Datenbankprogrammierung 3
P Mittels Java einen neuen MySQL User erstellen Datenbankprogrammierung 4
C Hibernate n:m mittels Zwischentabelle und bidirektionaler Zugriff Datenbankprogrammierung 2
A Problem mit Eintragen von Daten in eine Datenbank mittels DAO Datenbankprogrammierung 4
R MySQL Voraussetzungen für eine erfolgreiche Datenbankanbindung mittels JDBC Datenbankprogrammierung 2
T Mittels SQL-String ein Berechnung vornehmen Datenbankprogrammierung 2
D Mittels JUnit Reihe von DAOs testen Datenbankprogrammierung 10
J MYSQL-Zugriff mittels einer Java-Bean Datenbankprogrammierung 42
K Zugriff mittels JDBC funktioniert nur lokal Datenbankprogrammierung 5
M Mysql datenbank auslesen und mittels servlet wiedergeben Datenbankprogrammierung 3
W Problem bei Connection mit SQLServer-Datenbanke mittels Java Datenbankprogrammierung 2
K Stored Procedures, mittels Java Datenbankprogrammierung 8

Ähnliche Java Themen

Neue Themen


Oben