T3 : Lösung so richtig ?

[Hallo]

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]

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]

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

[kci]

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]

Was meinst du denn mit oBdA ?

[kci]

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