Komplexität: Übung 3, Beispiel 4

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!
Benutzeravatar
D'Angelo Russell
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 13. Apr 2016 12:56

Komplexität: Übung 3, Beispiel 4

Beitrag von D'Angelo Russell » 22. Mär 2017 09:30

Hallo zusammen, ich habe eine Frage zur oben genannten Aufgabe. Und zwar bin ich mir bei der Komplexität der Methode symdiff1 unsicher.

[n bezeichne hier die Anzahl der Elemente in a und m bezeichne die Anzahl der Elemente in b]

Meine Überlegungen sind wie folgt:
- in den beiden for-Schleifen für a und b wird jeweils ein Mal über die beiden Arrays iteriert. Somit entsteht nur für diese Iteration ein Aufwand von n bzw. m
- in den for-Schleifen wird dann n bzw. m mal die Methode searcher aufgerufen (auf jedem Element des betrachteten Arrays)
- die Methode searcher iteriert bei jedem Aufruf über das andere Array, d.h. beim Durchlauf von a iteriert searcher über das Array b und umgekehrt

=> für die Iteration über das Array a ergibt sich n + n * m [(Iteration über a) + (für jedes Element in a wird searcher aufgerufen, der dann jedes Mal über die Länge von b iteriert)]
=> für die Iteration über Array b ergibt sich m + m * n [(Iteration über b) + (für jedes Element in b wird searcher aufgerufen, der dann jedes Mal über die Länge von a iteriert)]

Machen meine Überlegungen Sinn?
Falls ja, wie setze ich diese einzelnen Bestandteile dann in die Gesamtkomplexität der Methode symdiff1 um?

Vielen Dank vorab für die Mühe!

D' Angelo Russell
I got ice in my veins! 8)

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Komplexität: Übung 3, Beispiel 4

Beitrag von Prof. Karsten Weihe » 22. Mär 2017 21:47

D'Angelo Russell hat geschrieben: Machen meine Überlegungen Sinn?
Ich würde sagen ja. :)

D'Angelo Russell hat geschrieben: Falls ja, wie setze ich diese einzelnen Bestandteile dann in die Gesamtkomplexität der Methode symdiff1 um?
Die beiden for-Schleifen in symdiff1 dominieren ja zusammen offensichtlich alle anderen Operationen asymptotisch. Also ist die asymptotische Komplexität von symdiff1 gerade die Summe aus denen der beiden Schleifen.


1. Worst Case:

Im Worst Case durchläuft searcher das ganze Array, das heißt, im Worst Case kostet ein Aufruf von searcher n bzw. m Iterationen in den beiden Schleifen. Da die beiden Schleifen in symdiff1 m- bzw. n-mal durchlaufen werden, lässt sich der Worst Case für symdiff1 damit nach oben abschätzen: O(m*n+n*m)=O(m*n).

In dem Fall, dass die beiden Arrays kein einziges Element gemeinsam haben, läuft die Schleife in searcher tatsächlich bei jedem Aufruf von searcher ganz durch a. Das heißt, wir haben einen Fall mit asymptotischer Komplexität m*n gefunden, und der Worst Case kann natürlich nicht besser sein. Daher lässt sich der Worst Case nach unten abschätzen: Omega(m*n).

Per Definition von Theta folgt aus beidem zusammen, dass der Worst Case in Theta(m*n) ist.


2. Best Case:

Auch im Best Case werden die beiden Schleifen in symdiff1 m- bzw. n-mal durchlaufen. Der Best Case von searcher ist der Fall, wenn x gleich ganz vorne im Array gefunden wird. Damit lässt sich der Best Case nach unten abschätzen: Omega(m+n). Für die weiteren Betrachtungen brauche ich eine Fallunterscheidung, wie der Input von symdiff1 genau spezifiziert ist.

(a) Falls die beiden Eingabearrays von symdiff1 Duplikate enthalten dürfen, ist der Fall möglich, dass sämtliche Komponenten beider Arrays nur einen einzigen Wert enthalten. In diesem Fall steigt die Schleife in searcher tatsächlich immer gleich in der ersten Iteration aus, und es ergibt sich m+n. Da der Best Case nicht schlechter sein kann, ist der Best Case in O(m+n). Wegen der Feststellung Omega(m+n) im letzten Absatz ist der Best Case insgesamt in Theta(m+n).

(b) symdiff1 kann aber auch so spezifiziert sein, dass in jedem der beiden Eingabearrays alle Elemente paarweise verschieden sein sollen. Dann sind die erlaubten Inputs für Fall (b) eine Teilmenge der möglichen Inputs für Fall (a). Der Best Case in (b) kann also nicht besser als der in (a) sein und lässt sich daher ebenfalls nach unten abschätzen: Omega(m+n).

Den Fall (b) kann man im Best Case aber noch schärfer abschätzen. OBdA sei m<=n.

Der Best Case in der ersten Schleife ist, dass die ersten m Elemente von b identisch mit den Elementen von a sind (in beliebiger Reihenfolge). Das heißt, im Durchschnitt wird die Schleife in searcher in der ersten Schleife von symdiff1 gerade m/2-mal durchlaufen.Da die erste Schleife m-mal durchlaufen wird, ergibt sich insgesamt für die erste Schleife: m^2. Die zweite Schleife wird n-mal durchlaufen, im Durchschnitt ebenfalls mindestens m/2 Iterationen in searcher. Das ergibt für die zweite Schleife n*m.

Für beide Schleifen zusammen ergibt sich zusammen Omega(m^2+m*n). Wegen m<=n ist das asymptotisch gleich Omega(m*n). Analoge Argumentation führt auch im Fall m>=n zu Omega(m*n). Da der Worst Case in Theta(m*n) ist und der Best Case nicht schlechter als der Worst Case sein kann, ist der Best Case in O(m*n), insgesamt also ebenfalls in Theta(m*n).

KW 8)

Antworten

Zurück zu „AuD: Theoretische Aufgaben“