Informatiker Board | Druckvorschau: Problem bei einer Komplexitätsaufgabe

Geschrieben von Info2014 am 11.01.2014 um 17:37:

Problem bei einer Komplexitätsaufgabe

Meine Frage:
Guten Abend miteinander,

ich stehe vor einem Problem bei folgender Aufgabe (siehe Bild). Zum angegebenen Aktivitätendiagramm soll der Worst-Case berechnet werden bzw. eine Formel angegeben werden, die den Worst-Case beschreibt ("die Schritte zählt").

Ich verstehe leider nicht so ganz wie ich die Formel ansetzen soll, dass die Formel am Ende ein "+3" enthält ist mir klar, weil sich dieser Bereich außerhalb der Schleifen befindet.

Die Lösung ist: 3n^2 + 8n + 3

Wobei ich wie bereits erwähnt nur die +3 am Ende nachvollziehen kann.

Es wäre sehr schön, wenn man mir in einfachen Worten eine allgemeine Vorgehensweise zeigen könnte um dieses Problem anzugehen..

Vielen Dank.

Meine Ideen:
Ich habe die einzelnen Schritte gezählt, allerdings weiß ich nicht welche Formeln ich anwenden soll um die Verschachtelungen richtig abzufangen.

Geschrieben von eulerscheZahl am 11.01.2014 um 18:14:

In der inneren Schleife (in meinem Anhang der linke Kreis) gibt es bis zu 6 Schritte: Abfrage von z = 0, Addition von r und z, Zuweisung für r, Inkrementieren und Zuweisung von j und danach noch ein Vergleich mit i.
Die äußere Schleife durchläuft die innere 6*i Mal, dazu kommen 5 Schritte in der außeren Schleife selbst.

Also $[latex]\sum\limits_{i=1}^n{(6\cdot i+5)} = 6\frac{n\cdot(n+1)}{2}+5n = 3n^2+8n[/latex]$
Dazu die 3 von den zwei Zuweisungen r:=0 und i:=i, sowie eine Abfrage i>n, gibt die von dir genannte Lösung

Geschrieben von Winfo2014 am 11.01.2014 um 20:48:

Vielen herzlichen Dank für deine Erklärung.

Jetzt ist mir ein Licht aufgegangen Daumen hoch

Geschrieben von Winfo2014 am 11.01.2014 um 22:34:

Neue Aufgabe, neues Glück

Ich habe jetzt mal versucht mich in der Materie zu vertiefen und bin nun wieder auf ein Problem gestoßen, das mich seit Stunden beschäftigt.

Neues Aktivitätendiagramm, aber gleiche Aufgabenstellung.

Die Lösung lautet: 5 + 5n + 12n^2
Ich komme aber auf: 5+11n+6n^2

Ich habe meinen Fortschritt im Screenshot dokumentiert...

Ich bedanke mich jetzt schon sehr für euren Support!!!

Viele Grüße
Winfo2014