Informatiker Board | Berechenbarkeits- und Komplexitätstheorie

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Problem bei einer Komplexitätsaufgabe

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Problem bei einer Komplexitätsaufgabe

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Info2014
Grünschnabel

Dabei seit: 11.01.2014
Beiträge: 1

Problem bei einer Komplexitätsaufgabe

Zitatantwort auf diesen Beitrag erstellen

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.

Info2014 hat dieses Bild (verkleinerte Version) angehängt:

11.01.2014 17:37

Nehmen Sie Info2014 in Ihre Freundesliste auf

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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

eulerscheZahl hat dieses Bild (verkleinerte Version) angehängt:

__________________
Syntax Highlighting fürs Board (Link)

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von eulerscheZahl: 11.01.2014 18:15.

11.01.2014 18:14

Nehmen Sie eulerscheZahl in Ihre Freundesliste auf

Winfo2014
Grünschnabel

Dabei seit: 11.01.2014
Beiträge: 2

Vielen herzlichen Dank für deine Erklärung.

Jetzt ist mir ein Licht aufgegangen Daumen hoch

11.01.2014 20:48

Nehmen Sie Winfo2014 in Ihre Freundesliste auf

Winfo2014
Grünschnabel

Dabei seit: 11.01.2014
Beiträge: 2

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

Winfo2014 hat diese Bilder (verkleinerte Versionen) angehängt:

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Winfo2014: 11.01.2014 22:35.

11.01.2014 22:34

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Problem bei einer Komplexitätsaufgabe