Laufzeitanalyse

paco89

Bekanntes Mitglied
hallo, ich hab folgende aufgabe(s.bild), die ich nicht lösen kann. kann mir da jmd. weiterhelfen, wie ich genau vorgehen muss? also keine lösungen angeben, sondern einfach nur hilfreiche tipps, was ich zu tun habe...



vielen dank schon mal im voraus
 

Anhänge

  • üb5.png
    üb5.png
    19,8 KB · Aufrufe: 52
M

Marcinek

Gast
Berechne die Anzahl der Rechenoperatoren in Abhängigkeit von n.

Dann kannst du nach Komplexitätsanlyse googeln.

Siehe auch O-Notation.
 

paco89

Bekanntes Mitglied
ja, also ich hab ein wenig gegoogelt und bin wie folgt an die sache rangegangen:

zunächst einmal bezeichnet x die anzahl der operationen(unbekannter wert). außerdem habe ich die beiden verschachtelten schleifen in innere und äußere schleife unterteilt:

innere schleife:

ich rechne ja in dem schleifenrumpf der inneren schleife: 2*result *2*result * ...* und das ganze halt x-mal bis die schleifenbedingung abbricht. also lautet die ungleichung die ich aufstelle:

(2*result)^x <= 0 , da 0 die abbruchbedingung ist.

auf beiden seiten mache ich log() und daraus wird:

log((2*result)^x) <= log(0)

<=> x* log((2*result)) <= log(0)

so und ab hier habe ich ein problem, denn log(0) ist ja nicht definiert. wie muss ich weitermachen?


bei der äußeren schleife habe ich dasselbe problem:

result*result*...* <=0

<=> log(result^x) <= log(0)
<=> x*log(result) <= log(0)

hier habe ich dasselbe problem....;(
 

XHelp

Top Contributor
Schau doch einfach, was in der Schleife passiert. Wo siehst du die Stelle, dass der Wert von result eine Rolle spielt?
 

paco89

Bekanntes Mitglied
ach so, okay...ach darauf muss ich achten, hmmh...also, dann muss ich das i nehmen, bzw. i/2 oder?


also dann würde meine rechnung lauten:

i/2 * i/2 *.... und das ganze x-mal, wobei die abbruchbedingung 0 ist, also:

(i/2)^x <=0

<=> log((i/2)^x) <= log(0)


ist das so richtig ? wenn ja, so habe ich doch wieder log(0), was ein problem darstellt, was mach ich damit?
 

XHelp

Top Contributor
statt result einfach irgendwo i/2 hinsetzen wird die Aufgabe auch nicht lösen.

Überlege zuerst wie oft die äußere Schleife läuft
 

paco89

Bekanntes Mitglied
ja, die äußere wird ja so oft durchlaufen bis die schleifenbedingung nicht mehr erfüllt ist, oder wie darf ich das verstehen?
 
M

Marcinek

Gast
Tipp:

Schreibedas Programm in Java und gib für value verschiedene werte ein.

Dann siehst du wie oft die äußere Schleife in Abhängigkeit von value durchlaufen wird.

Das Ergebnis dieser überlegung muss eine Zahl sein.

Also n n² oder n³ oder oder oder
 

XHelp

Top Contributor
ja, die äußere wird ja so oft durchlaufen bis die schleifenbedingung nicht mehr erfüllt ist, oder wie darf ich das verstehen?

Also lautet die gesamte Antwort für deine Aufgabe: das Programm braucht so viele Schritte, wie es eben Bracht, der Wert liegt so zwischen 0 und Unendlichkeit... :bahnhof:

Anders gefragt: finde raus, wie oft
Code:
exakt
die äußere Schleife durchlaufen wird, anhand von einem Parameter. Dieser Parameter sollte sinnvoller Weise
Code:
value
sein
 

cmrudolph

Gesperrter Benutzer
Ich habe jetzt extra über eine Woche gewartet, da ich denke, dass die Zeit für die Hausaufgabe mittlerweile abgelaufen sein sollte.
Dennoch habe ich mich im Verlaufe des Threads gefragt, wie man denn auf die Laufzeit des Algorithmus kommt, wenn man zuerst die Laufzeit der äußeren Schleife bestimmt.
Die Laufzeit der äußeren Schleife liegt ja in O(log n) (etwas genauer wohl in floor(ld(value))+1).

Ich habe die Komplexität folgendermaßen bestimmt:
Die innere Schleife läuft i-mal durch.
i entwickelt sich wie folgt bezogen auf die äußere Schleife:
0. Durchgang: i=n
1. Durchgang: i=n*1/2
2. Durchgang: i=n*1/2*1/2
j. Durchgang: i=n*(1/2)^j

Daraus lässt sich für die ersten j Durchläufe die Reihe
attachment.php

aufstellen (wäre für die korrekte Aufgabenlösung mittels vollständiger Induktion zu beweisen).

Da dies eine geometrische Reihe ist, kann man den Grenzübergang wie folgt ermitteln:
attachment.php


Ergo liegt die Komplexität des Algorithmus in O(2n)=O(n).

Wenn man ein kleines Testprogramm schreibt, was die inneren Schleifendurchläufe zählt, dann sieht man, dass 2n tatsächlich richtig ist. Abhängig vom n liegt es teilweise auch unter 2. Je größer allerdings das n, desto besser passt die Näherung.

Um jetzt von der Komplexität der äußeren Schleife O(log n) auf O(n) zu kommen, müsste man irgendwie einen Korrekturterm bekommen (n/log n ?). Wie bekommt man den dann?
 

Anhänge

  • CodeCogsEqn1.gif
    CodeCogsEqn1.gif
    832 Bytes · Aufrufe: 50
  • CodeCogsEqn2.gif
    CodeCogsEqn2.gif
    1,6 KB · Aufrufe: 50

cmrudolph

Gesperrter Benutzer
Da hier bisher noch keine weitere Antwort kam, mich die andere Lösung aber interessiert, pushe ich hier einmal.
Wie wäre der Lösungsweg, nachdem man zuerst die Komplexität der äußeren Schleife bestimmt hat?
 
S

SlaterB

Gast
denke nicht dass das funktionieren kann, denn die innere Schleife hat keine relativ konstante Anzahl an Schritten,
so dass man diese einfach mit der Zahl der Durchläufe multiplizieren könnte,

nur die innere Schleife betrachtet muss man n als Aufrundung annehmen, im Produkt n log(n) dann zu groß,
man weiß dass es kleiner wird, kann das aber nicht seriös ohne Betrachtung der gesamten Doppelschleife ausrechen,

wenn man aber alles betrachtet, hat man die äußere Schleife quasi und real mit drin, dann kommt man auf n auf deinen anderen Weg,
und erst dann könnte man das in das Pseudoprodukt log n * n/ log n aufteilen, helfen wird das dann aber nicht mehr

edit:
hilfreich noch dazu, denke ich:
würde i in der äußeren Schleife von 0-n durchlaufen, wäre die innere Schleife immer noch dieselbe,
das Endergebnis aber ein anderes, was sich nicht allein durch n statt log n für die äußere Schleife errechnet,
das Zusammenspiel ist wichtig, hier wäre dann die Schätzung n für die innere Schleife letzlich quasi richtig,
dennoch nicht besser als vorher
 
Zuletzt bearbeitet von einem Moderator:

Neue Themen


Oben