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.
T3 : Lösung so richtig ?
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!
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!
Re: T3 : Lösung so richtig ?
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.
Re: T3 : Lösung so richtig ?
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..

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..


Re: T3 : Lösung so richtig ?
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
Re: T3 : Lösung so richtig ?
Was meinst du denn mit oBdA ?
Re: T3 : Lösung so richtig ?
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