Informatiker Board | Berechenbarkeits- und Komplexitätstheorie | Problem bei einer Komplexitätsaufgabe

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

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 4 Beiträge
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 Winfo2014 hat diese Bilder (verkleinerte Versionen) angehängt:
Winfo2014	Vielen herzlichen Dank für deine Erklärung. Jetzt ist mir ein Licht aufgegangen !
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 eulerscheZahl hat dieses Bild (verkleinerte Version) angehängt:
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. Info2014 hat dieses Bild (verkleinerte Version) angehängt: