T3 : Lösung so richtig ?

Bei Postings zu Aufgabe Nr. x auf Blatt Nr. y lassen Sie Ihr Betreff bitte mit "y.x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Aufgabe Nr. x auf Blatt Nr. y lassen Sie Ihr Betreff bitte mit "y.x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
Hallo
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 162
Registriert: 22. Apr 2015 19:03

T3 : Lösung so richtig ?

Beitrag von Hallo » 26. Aug 2016 14:33

Hallo,
Hat jemand vielleicht eine Musterlösung der Übungsaufgabe 4 und 5 mit Erklärung, wie er auf die Lösung gekommen ist ?

Also ich würde so dran gehen:

Der Algorithmus kriegt 2 Listen a und b übergeben. Im worst case muss der Algorithmus die zwei Listen komplett durchgehen. (Angenommen, der beste Fall wäre eine Liste davon wäre leer, wird nur die nicht leere Liste als Ausgabe kommen).
Um die 2 Listen durchzugehen, müssen die 2 for-Schleifen komplett durchlaufen, bis i = a.length(n als Variable), bzw b.length(m als Variable).
Ich würde sagen die Methode searcher ist von Länge der Eingabeliste abhängig und ist eine Konstante ? Obwohl man auch als Gegenargument sagen kann, dass die Methode allein nochmal n * m mal läuft.

Also setzen wir für die 1. for-schleife n als Variable, da ich für (a.length n als Variable habe, siehe oben) und für die innere while Schleife (in der searcher Methode) die Variable der 2. Liste m, würde für die 1. for-Schleife n*m rauskommen, bzw der 2. for-Schleife m*n.

Am Ende kommt man dan auf O((n*m) + (m*n)) = O(2nm) = O(nm), da ja die Konstanten wegfallen.

Macht meine Lösung Sinn ?
Viele Grüße.

kci
Windoof-User
Windoof-User
Beiträge: 24
Registriert: 21. Apr 2016 20:54

Re: T3 : Lösung so richtig ?

Beitrag von kci » 27. Aug 2016 13:45

Für Beispiel 4 klingen deine Überlegungen richtig für mich, Beispiel 5 hat aber eine andere Komplexitätsklasse, zumindest hatte ich mir damals eine andere überlegt. Und noch berücksichtigen, dass Komplexitätsklassen eigentlich Theta(...) sind und nur falls Theta nicht bestimmt werden kann durch O(...) abgeschätzt werden.

Hallo
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 162
Registriert: 22. Apr 2015 19:03

Re: T3 : Lösung so richtig ?

Beitrag von Hallo » 27. Aug 2016 16:17

Für Beispiel 5 habe ich auch die gleiche Komplexität.
Hat jemand vielleicht eine andere Lösung ?




Warum Antwortet der Professor Weihe eigentlich nicht auf den Beitrag ? Sine Hilfe/Korrektur würde uns allen was bringen.. :| :roll:

kci
Windoof-User
Windoof-User
Beiträge: 24
Registriert: 21. Apr 2016 20:54

Re: T3 : Lösung so richtig ?

Beitrag von kci » 27. Aug 2016 17:55

was ist denn dein Worstcase für Beispiel 5? Ich hatte mir dafür überlegt, dass keine Zahl, die in a enthalten ist auch in b enthalten ist, wenn Länge a=n und Länge b=m sind durchlaufen wir im Worstcase dann immer die beiden else if Bedingungen bis wir alle Zahlen von entweder a oder b in das neue Array eingetragen haben, nehmen wir mal, dass sei oBdA a gewesen, dann haben wir bisher n+x schritte durchlaufen, wobei x die zahlen aus b sind, die wir bisher ins neue array eingetragen haben, dann greift die if Bedingung if(i==a.length) und die restlichen m-x zahlen aus b werden ins neue array eingetragen, dass sind nochmal m-x schritte, insgesammt also n+x-x+m=n+m, damit hatte ich mir als Komplexität Theta(n+m) für Beispiel 5 überlegt

Hallo
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 162
Registriert: 22. Apr 2015 19:03

Re: T3 : Lösung so richtig ?

Beitrag von Hallo » 4. Sep 2016 19:29

Was meinst du denn mit oBdA ?

kci
Windoof-User
Windoof-User
Beiträge: 24
Registriert: 21. Apr 2016 20:54

Re: T3 : Lösung so richtig ?

Beitrag von kci » 5. Sep 2016 00:02

Abkürzung für ohne Beschränkung der Allgemeinheit, bedeutet hier, dass ich den 2.Fall ,dass b als erstes durchlaufen worden ist, nicht näher betrachte, weil die Argumentation vollkommen analog nur mit vertauschten Rollen funktioniert

Antworten

Zurück zu „AuD: Theoretische Aufgaben“