Wie kann ich die Komplexität bestimmen?

[BlueMoon92]

Hallo,

ich versuche gerade herauszufinden, wie man die Laufzeit von einem Code "ablesen" kann. Wie finde ich heraus, was die Funktion, die Anzahl der Schritte und die Komplexitätsklasse (O-Notation) von so einem Code ist? Muss ich bei so einem Code drauf achten, was übergeben wurde (hier: n) oder was zurückgeliefert (hier: z) wird, um die oben genannten Sachen herauszufinden? Worauf sollte ich auf jeden Fall achten?

	

public static int m1(int n) {

   int z = 0;


   while (n > 1) {

      n = n / 2;

      z++;

   }


   return z;

}

public static int m3(int n) {

   int t = 1, z = 0;


   while (n > 0) {

      n = n - t;

      t = t + 2;

      z++;

   }


   return z;

}

Also ich muss jetzt ganz ehrlich sagen, dass ich keine Ahnung habe wie man an so eine Aufgabe rangeht. Deswegen habe ich jetzt erstmal die Werte 1-5 und 10 für n eingesetzt und handschriftlich den Code selber "ausgeführt". Bei m1 komme ich auch auf log2(n). Aber bei der anderen Aufgabe habe ich keine Ahnung. Kann mir jemand erklären, wie ihr bei solchen Aufgaben vorgeht? Habe auch die folgenden Ergebnisse erhalten: m1) n: 1 2 3 4 5 ... 10 z: 0 1 1 2 2 ... 3 Laufzeit: log2(n) m3) n: 1 2 3 4 5 ... 10 z: 1 2 2 2 3 ... 4 Laufzeit: ? Die nächste Aufgabe wäre dann die hier gewesen..

public static int m4(int n) {

   return m3(m1(n));

}

[lilith2k3]

Ich bin jetzt auch kein Mathe-Genie - mein Abi war 1996 - aber ich würde stumpf iterativ an die Sache rangehen:

Beispiel m3:

Wenn ich mal beide Wertereihen von Dir als korrekt annehme, dann sieht es wie folgt aus:

n: 1 2 3 4 5 ... 10

z: 0 1 1 2 2 ... 3

Erste Arbeitshypothese O=n. Ist zwar grob, aber sollte hinhauen. n wird nie überschritten.

Zweite Hilfshypothese ergibt sich aus dem Ergebnis von m1 log2(n).

Wenn log2(n) stets kleiner als n ist, fällt (1) raus. Das könnte man jetzt mit vollständiger induktion beweisen, oder mal gerade da gucken: log2(x)<x - Wolfram|Alpha

Scheint zu passen.

Wenn man jetzt die beiden Ergebnisreihen anguckt:

m1 z: 0 1 1 2 2 ... 3

m3 z: 1 2 2 2 3 ... 4

So fällt auf, dass da kaum Unterschiede sind.

Das heißt man könnte sagen m3 ~ C*m1, folglich würde ich die in die gleiche Komplexitätsklasse n * log (n) stecken.

Aber das nur mal so aus der Hüfte geschossen. Wenn flashpixx den Thread findet, kann der das widerlegen oder untermauern - je nachdem, ob ich jetzt Lötzinn erzählt habe *g*

OT: Oh Mann, Matheabi vor 18 Jahren ...

[flashpixx]

Man bestimmt ganz normal die "Laufzeit" z.B. in dem man für jeden Befehl eine Laufzeit vergibt z.B. eine Wertezuweisung i=1 einfach 1 Zeiteinheit definieren. Schleifen entsprechend der Iterationsanzahl mal dem Inhalt. Danach macht man ganz klassisch einen Induktionsbeweis von n nach n+1 und erhält die Komplexitätsklasse. Da der Code aber meist einen konstanten Teil enthält, und die O-Notation (Landau-Notation) immer ein worst-case Szenario beschreibt, kann man den konstanten Faktor - meist mit c bezeichnet - ignorieren also ganz korrekt müsste es z.B. lauten O(c*n^2) man schreibt aber verkürzt O(n^2).

Wenn flashpixx den Thread findet, kann der das widerlegen oder untermauern - je nachdem, ob ich jetzt Lötzinn erzählt habe *g*

OT: Oh Mann, Matheabi vor 18 Jahren ...

Mein Abi ist 14 Jahre her :-) Aber ich habe den Thread gefunden und ergänze mal.

@Topic: Gehe beide Quellcodes unabhängig voneinander durch und berechne erst einmal die konkrete Laufzeit in Abhängigkeit von n, da bekommt man dann einen konkreten Wert heraus in dem n als Variable vor kommt. Darauf basierend dann einmal für n=1 das ganze zeigen (Induktionsanfang) und dann für n nach n+1 (vollständige Induktion) den Induktionsschritt durchführen.

Bearbeitet 16. August 2014 von flashpixx

[Gast]

Der klassische Weg und für alle Mathematiker und die theoretische Informatik ist korrekt. Aber bei deinem ersten Quellcode sehe ich auf Anhieb das es O(log(n)) ist. Wie ich darauf komme: 2/2=1 damit ist Schleife beendet log_2(2)=1. Gleiches Beispiel für 4, nach zwei Schleifendurchkäufen ist Schluss log_4(2).

Beim zweiten Versuc hulft die Reihenentwicklung 1+3+5+7+...+2n+1 vielleicht weiter