Komplexität

[javacc123]

Hallo liebes Forum,

Ich versuche zur Zeit mich mit dem Thema Aufwand und Komplexität eines Algorithmus zu beschäftigen, doch leider vergeblich.
Es geht mir um die O-Notation. Wie kann ich diese Schrittweise selbst aufstellen.

Beispiel:

int sum=0;
for (int i=1;i<=n;i++);
sum+=i*i;

return sum;

Also wie ich es verstanden habe geht es um Durchläufe allgemein die ein Algorithmus braucht.
Hier in dem Fall betrachte ich die for-Schleife, da dort es dort auf die Schleifendurchläufe ankommt wie lang mein Algorithmus braucht, dort verändert sich etwas (i) bis der Vergleich (i<=n) nicht mehr stimmt.
Die anderen Zeilen sind nur Konstanten, wie Initialisierung, Rückgabe etc.

Soweit richtig?

Wie komme ich jetzt zum Ergebnis also wie rechne ich das?

mfg

 

[InfectedBytes]

deklarationen etc. brauchen konstante Zeit => O(1)
Die schleife läuft von 1 bis n => O(n)
innerhalb der Schleife ist wieder nur ein Ausdruck mit konstanter Zeit => O(1)

Zusammen hast du also: O(1) + O(n) * O(1)
Und das lässt sich vereinfachen zu: O(1) + O(n)
Und das lässt sich wieder vereinfachen zu O(n)

 

[MWin123]

@InfectedBytes
i*i wäre doch O(x^2) oder irre ich mich?

 

[InfectedBytes]

nein, es ist nur eine multiplikation, welche O(1) kostet. Da dieser Ausdruck in jedem Schleifendurchlauf geschieht, hat die ganze Schleife kosten von O(n)

auf O(n^2) würde man z.B. kommen, wenn man zwei for-Schleifen schachtelt:

for(int x=0; x<n; x++){
  for(int y=y; y<n; y++) {
    // ....
  }
}

 

[javacc123]

Also läuft die Schleife von 1 bis n wegen i=1 und i<=n?

Kann man sagen, es geht also nur um die Ausdrücke(hier n) die man eingibt und verglichen werden?
Kann ich sagen, dass jede forschleife die von n abhängt also O(n) ist?

mfg

 

[InfectedBytes]

Also läuft die Schleife von 1 bis n wegen i=1 und i<=n?

ja, die schleife läuft von 1 bis n

Kann man sagen, es geht also nur um die Ausdrücke(hier n) die man eingibt und verglichen werden?

nicht direkt. Im Grunde geht es immer nur um schleifen und rekursion, also wielange die Schleifen laufen, bzw. wie oft rekursion auftritt.

Kann ich sagen, dass jede forschleife die von n abhängt also O(n) ist?

nein, es kommt auf die schleife an:

for(int i = 0; i< n; i++) { ... } // O(n)
for(int i = 0; i < Math.sqrt(n); i++) { ... } // O(wurzel(n))

Außerdem kann i ggf noch in der schleife verändert werden.

Und in der Schleife können noch weitere Schleifen sein, siehe beispiel aus meinem anderen post

 

[javacc123]

Ok bisher denke ich, dass ich es teilweise verstanden habe.
Hier noch ein Beispiel:

public static boolean doit(char[] a, char[] b) {
if(a.length != b.length){
return false;
}
return doit(a,b,0);
}

private static boolean doit(char[] a, char[] b, int ax) {
if (ax == a.length){
return true;
}
if (a[ax] == b[ax]) {
return doit(a,b,ax + 1);
}
return false;

Hier betrachte ich also nur die Rekursion, in dem Fall doch die 2. Methode doit.
Dort wird doch so lange die 2. if bedingung durchgeführt bis ax == a.length erreicht hat und falls das bei jedem Durchlauf nicht der Fall ist wird ax + 1 addiert.

Also läuft die Bedinung von 0 bis a.length? Somit O(char[]a) oder O(a.length) ?

mfg

 

[InfectedBytes]

worstcase laufzeit von O(a.length)

 

[javacc123]

Könntest du das nochmal bitte genauer erklären, so wie oben bei der for-schleife(in den einzelnen Schritten)?
Wäre sehr hilfreich.

mfg

 

[InfectedBytes]

zu prüfen, ob die ax==a.length ist, ist konstanter Aufwand => O(1)
wenn a[ax] == b[ax] ist, so ruft sich die methode selbst auf, jedoch mit um eins erhöhtem ax.
Da ax niemals reduziert wird, sondern immer um genau eins erhöht wird, kann sich die methode eben maximal a.length mal selbst aufrufen. Denn dann ist ax == a.length und die methode wird verlassen
=> O(n) viele rekursive aufrufe.
Es können natürlich auch weniger aufrufe sein, falls nämlich a[ax] != b[ax] ist, so wird direkt returned.

Zusammenfassend: Maximal O(n) viele Aufrufe, in denen jeweils nur konstanter Aufwand O(1) betrieben wird => O(n) * O(1)
=> worstcase Laufzeit O(n)

 

[JStein52]

Du betrachtest ja immer nur die Laufzeitkomplexität, nicht Speicher etc.
Und dafür musst du dir immer die Frage beantworten wie ist die Laufzeit abhängig von irgendwelchen anderen Werten, hier von der Länge des Arrays a .. Das Prinzip ist das gleiche wie bei einer Schleife. Wenn das Array a um eins grösser wird hast du eine Rekursion mehr. Also O(a.length) !

 

[javacc123]

Ok verstanden.

Danke für die Antworten.