Probleme bei Berechnung der Komplexität

[KäseSahne]

Hallo,

ich brauche mal wieder eure Hilfe. Es geht um die Berechnung der Laufzeitkomplexität (O-Notation). Ich möchte damit Algorithmen vergleichen.
Meine erste Frage bezieht sich darauf, wie man die Komplexität eines Algorithmus berechnet, der von zwei Parametern abhängig ist. Hier mal ein Beispiel:

for(int i = 0; i < m; i++){
	for(int j= 0; j < n; j++){
		doSth();
	}
}

Wie man sieht, hängt die Anzahl der Aufrufe von "m" und "n" ab. Die Methode doSth() würde ja m*n-Mal aufgerufen. In welcher Komplexitätsklasse würde sich denn der Algorithmus befinden? Es hängt ja maßgeblich von der Größe von m ab. Ist m <= n, dann müsste die Komplexität quadratisch sein. Im Fall von m > n ist sie kubisch. Was nimmt man denn allg. für die Komplexität dieses Algorithmus an?

Meine zweite Frage betrifft ein weiteres Beispiel. Den Ablauf gebe ich in Pseudocode an:

int[] spielfeld = new int[m];
Spieler[] spielerAry = new Spieler[n];

erstelle Spieler;
berechne Felder der Spieler;

ArrayList<int[]> zustandsListe = new ArrayList<int[]>();

while(min. ein Spieler deaktiviert wurde){
	while(aktueller Zustand von spielfeld nicht in zustandsListe){
		aktuellen Zustand von spielfeld in zustandsListe schreiben;
		for(Spieler player : spielerAry){
			if(min. ein Feld von player in spielfeld blockiert){
				prüfe, ob player alle blockierten Felder günstiger erledigen kann als die eingetragenen Spieler;
				if(player kann alle Felder günstiger erledigen){
					lösche alle Spieler aus spielfeld, die player blockiert haben;
					Felder von player in spielfeld blockieren;
				}				
			}
		}			
	}
	alle Spieler, die in spielfeld stehen, deaktivieren;
	für jeden aktiven Spieler neue Felder berechnen (diese Felder müssen im Spielfeld noch frei sein);
	zustandsListe zurücksetzen;
}

Es gibt ein "spielfeld", das aus m Feldern besteht. Außerdem gibt es n Spieler. Für jeden Spieler werden zufällig Felder gewählt, die er im "spielfeld" belegen soll (Anzahl zufällig). Des Weiteren gibt es eine "zustandsListe", die an bestimmten Stellen im Algorithmus den Zustand des Spielfelds speichert.

Zu Beginn sind alle Spieler aktiv. Der Algorithmus wird solange ausgeführt, bis kein Spieler mehr deaktiviert wurde (erste while-Schleife). In der zweiten while-Schleife wird geprüft, ob der aktuelle Zustand des "spielfelds" in der "zustandsListe" steht. Ist das nicht der Fall, wird der aktuelle Zustand in die "zustandsListe" geschrieben. Jetzt wird das Spieler-Array durchlaufen. Für jeden aktiven Spieler wird geprüft, ob die Felder, die er im "spielfeld" belegen möchte, frei sind. Wird min. ein Feld von einem anderen Spieler blockiert, wird geprüft, welcher der Spieler dafür am günstigsten ist. Nur wenn der aktuelle Spieler (player) für alle blockierten Felder am günstigsten ist, wird er in das "spielfeld" eingetragen. Die Spieler, die ihn blockiert haben, werden vom "spielfeld" gelöscht.
Das wird so oft wiederholt, bis das "spielfeld" einen bereits bekannten Zustand angenommen hat. Daraufhin werden die Spieler, die jetzt noch im "spielfeld" stehen, deaktiviert, d.h. sie fließen nicht weiter in die Berechnungen mit ein. Für die noch aktiven Spieler werden wieder zufällig Felder gewählt, die sie belegen sollen. Die "zustandsListe" wird zurückgesetzt und alles beginnt von vorne.


Ich hoffe, dass ihr den Algorithmus halbwegs nachvollziehen konntet. Auch hier ist mein Problem die Berechnung der Komplexität. Ich habe keine Ahnung, wie ich mit den beiden while-Schleifen umgehen soll.

Ich hoffe, dass ihr mir ein paar Tipps geben könnt, wie man an das Problem rangeht.

Vielen Dank im Voraus!

 

[dcc]

Es gibt immer: best case, average und worst case Laufzeiten.


Wenn du die Formel hast, dann lässt zum Schluss einfach die Konstanten und Multiplikationen weg.
Ist der Rechner schneller als der vorherige, dann sagt dir eine Multiplikation nix. Konstanten sind so klein dass man sie vernachlässigt.

 

[KäseSahne]

Hallo dcc,

vielen Dank für deine Antwort.
Im ersten Fall gibt es doch kein best case und worst case, oder? Die Methode wird immer n*m mal aufgerufen. Für die Komplexität muss man doch eine Funktion bestimmen, die die Obergrenze darstellt, richtig? Und das hängt doch entscheidend von m ab. Angenommen m wäre 1 und n > 0, dann würde die Methode n mal ausgeführt, also O(n). Sobald aber m > 1 wäre, dann würde ja g(n) nie die Obergrenze darstellen.
Und dann gibt es außerdem die Fälle m > n und m < n.
Würde man immer knallhart sagen, dass m eine Konstante ist und es somit eine Komplexität von O(n) hat?

Im zweiten Fall müsste der best case O(n) betragen. Ist das richtig? Die for-Schleife wird auf alle Fälle mindestens 2 mal ausgeführt, bis es zu einem doppelten Zustand kommen kann. Unter der Annahme, dass die äußerste Schleife beendet wird, wenn alle Spieler inaktiv sind oder alle Felder des Spielfelds belegt sind. Was mir da Probleme bereitet, ist der worst case.

 

[Alex Unkreativ]

Hallo,
Meine erste Frage bezieht sich darauf, wie man die Komplexität eines Algorithmus berechnet, der von zwei Parametern abhängig ist. Hier mal ein Beispiel:

for(int i = 0; i < m; i++){
	for(int j= 0; j < n; j++){
		doSth();
	}
}

Wie man sieht, hängt die Anzahl der Aufrufe von "m" und "n" ab. Die Methode doSth() würde ja m*n-Mal aufgerufen. In welcher Komplexitätsklasse würde sich denn der Algorithmus befinden? Es hängt ja maßgeblich von der Größe von m ab. Ist m <= n, dann müsste die Komplexität quadratisch sein. Im Fall von m > n ist sie kubisch. Was nimmt man denn allg. für die Komplexität dieses Algorithmus an?

Du beantwortest deine Frage fast schon selber: Die Komplexität ist O(n*m). Wenn du jetzt weisst, dass generell n > m gilt, dann ist die Komplexität quadratisch in n, also O(n^2). Warum sie kubisch sein sollte, sehe ich nicht. Natürlich kann O(n) = O(m^2) gelten, dann könntest du die Laufzeit durch O(m^3) abschätzen, sie wäre dann kubisch in m. Andersherum könntest du sie in diesem Fall aber auch, und das würdest du eher tun, durch O(n^2) oder einen noch geringeren Wert abschätzen.

Wichtig ist, dass die Abschätzung für alle Fälle gelten muss, denn O ist eine asymptotisch obere Schranke. Eine Worst Case Abschätzung: Mag es auch nur einen Fall geben, wo die Laufzeit > O(n^2) ist, ist die Abschätzung O(n^2) falsch. (Als kluger Algorithmenbastler würdest du für diesen Fall dann eine Sonderbehandlung programmieren und könntest dann die Abschätzung O(n^2) vornehmen). Beispielsweise gibt es viele NP-schwere Probleme, die für fast jede Eingabe polynomiell gelöst werden können, aber für eine geringe Anzahl eben doch eine nicht polynomielle Laufzeit haben. Das Rucksackproblem ist dafür ein klassisches Beispiel, es ist nur deshalb NP-vollständig, weil die Größenunterschiede zwischen den Objekten exponentiell sein können, was insgesamt zu einer superpolynomiellen (also nicht mehr polynomiellen) Laufzeit führt.
Deshalb ist z. B. auch die Aussage, dass deine Programme eine Laufzeit O(2^n) haben völlig korrekt, aber sinnfrei. Ziel ist es immer eine obere Schranke zu finden, die so knapp wie möglich über dem Maximalwert liegt.

Das heißt, in deinem Beispiel gehst du erstmal von O(m*n) aus und guckst dann weiter, ob du m oder n näher einschränken kannst. Z. B. könnte m eine Konstante sein oder durch eine unheimlich große Konstante abschätzbar sein (z. B. m ist egal für welche Eingabe geringer als 10^112338912112), dann wäre die Laufzeit O(n). Oder du kannst zeigen, dass m <= log n ist, dann wäre deine Abschätzung O(n*log n). Und das kann in realen Anwendung den Unterschied zwischen nutzbar und viel zu lang bedeuten. Setze einfach mal große Zahlen für m und n ein, sehe diese als Anzahl der Rechenschritte und guck dir den Unterschied an. Deshalb ist es auch so relevant die Laufzeitkomplexität auch nur minimal zu drücken: Jede geringfügige Verringerung in der Abschätzung von m kann für große Eingaben einen drastischen Unterschied machen. Das ist auch der Grund, warum Konstanten und seien sie auch unfassbar groß, ignoriert werden: Es gibt immer den Punkt, wenn man die Problemgröße erhöht, wo die Konstanten keine signifikante Rolle mehr spielen.

Meine zweite Frage betrifft ein weiteres Beispiel. Den Ablauf gebe ich in Pseudocode an:

while(min. ein Spieler deaktiviert wurde){
	while(aktueller Zustand von spielfeld nicht in zustandsListe){
		aktuellen Zustand von spielfeld in zustandsListe schreiben;
		for(Spieler player : spielerAry){
			...			
			}
		}			
	}
}

Ich durchschaue dein Programm nicht, aber du kannst immer so vorgehen: Du hast ja schon selber festgestellt, dass die Zahl der Schleifendurchläufe multipliziert werden muss. Und genau so gehst du jetzt auch hier vor: Du betrachtest jede Schleife einzeln und schätzt nach oben ab, wie oft sie maximal durchlaufen wird. Diese Werte multiplizierst du und hast im Grunde deine Laufzeit. Die Kunst ist natürlich jetzt nicht ein Ergebnis O(n*m*l*k) zu haben, sondern die einzelnen Werte zueinander in Beziehung zu setzen, also z. B. zu merken: m < log n, l = Konstant und O(k) = O(n), denn dann hast du als Ergebnis O(n^2 * log n). Wenn du vor oder nach der Schleife noch Berechnungen hast und du weißt, dass die in jedem Fall eine geringere Komplexität haben, dann fallen sie weg. Warum? Ganz einfach, du könntest das Programm insgesamt dann durch O(2 * n^2*log n) abschätzen, hättest also nur eine Konstante mehr und die fällt weg. Mit ein bisschen Übung wirst du dir so ein Programm nehmen und direkt die relevanten Teile extrahieren. In diesem Fall wohl nur die Schleifen und auch dort sehen: was ist konstant und fällt weg und wie lassen sich die einzelnen Durchläufe durch eine oder zwei Variablen m und n abschätzen.

 

[KäseSahne]

Vielen Dank für deine sehr ausführliche Antwort, Alex.
Der Grund, weshalb ich gedacht habe, dass die Komplexität kubisch ist, ist der Fall, wenn m > n ist. Ich kann leider nicht pauschal sagen, dass m < n immer gilt, da das vom Benutzer abhängig ist. Ich kann nur sicher sagen, dass m > 0 sein muss.

Kurz etwas zum Zweck des ersten Algorithmus: Dieser Algorithmus ist ein heuristischer Algorithmus zur Lösung eines Tourenplanungsproblems. Der Benutzer kann mit m angeben, wie oft versucht werden soll, die Lösung zu verbessern.

Der zweite Algorithmus bezieht sich auch auf ein Tourenplanungsproblem. Ich habe versucht, ihn grob mit dem Pseudocode auf einer anderen Ebene zu erklären, das ist mir wohl nicht wirklich gelungen .

Entschuldigung, wenn ich mich etwas blöd anstelle, aber Komplexitätsberechnung war nie wirklich mein Fall.

 

[Alex Unkreativ]

Vielen Dank für deine sehr ausführliche Antwort, Alex.
Der Grund, weshalb ich gedacht habe, dass die Komplexität kubisch ist, ist der Fall, wenn m > n ist. Ich kann leider nicht pauschal sagen, dass m < n immer gilt, da das vom Benutzer abhängig ist. Ich kann nur sicher sagen, dass m > 0 sein muss.

Kurz etwas zum Zweck des ersten Algorithmus: Dieser Algorithmus ist ein heuristischer Algorithmus zur Lösung eines Tourenplanungsproblems. Der Benutzer kann mit m angeben, wie oft versucht werden soll, die Lösung zu verbessern.

Dann kannst du nicht mehr über die Laufzeit des Algorithmus aussagen, als dass sie O(m*n) entspricht. Quadratisch oder kubisch bezieht sich auf eine einzelne Eingabe. Wenn du hier zwei Eingabewerte hast, die du auch nicht in einen Zusammenhang stellen kannst, dann kannst du auch keine weitergehende Aussage treffen. Denn warum sollte der Nutzer nicht 2^n als Wert eingeben, dann wäre die Laufzeit exponentiell in n.

 

[KäseSahne]

Danke, hast mir sehr weitergeholfen.

Gruß

 

[Highchiller]

Ein kleiner Tipp noch am Rande. Wenn du dir nicht sicher sein solltest ob eine Funktion f auch in O(g) liegt, hilft dir sicherlich die mathematische Definition weiter. Die findest du ganz übersichtlich bei Wikipedia: Landau-Symbole.

Wenn du dich mit den mathematischen Notationen auskennst kannst du einfach überprüfen ob f in O(g) liegt indem du es in die Definition einsetzt und rechnest.

Auf die Art kannst du dann auch ganz leicht beweisen das zum Beispiel 2n auch in O(n) liegt. Genauso wie 2+n auch in O(n) liegt. Und so weiter.