Problem bei einer Komplexitätsaufgabe

Neue Frage »

Auf diesen Beitrag antworten »
Info2014 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.
 
Auf diesen Beitrag antworten »
eulerscheZahl

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
Auf diesen Beitrag antworten »
Winfo2014

Vielen herzlichen Dank für deine Erklärung.

Jetzt ist mir ein Licht aufgegangen Daumen hoch !
Auf diesen Beitrag antworten »
Winfo2014 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
 
 
Neue Frage »
Antworten »


Verwandte Themen