Laufzeitanalyse

[Nesli]

Hallo Zusammen,

ich habe Probleme mit Laufzeitanalysen. Ich hab da ein gegebenen Java-Code, bei dem ich die Laufzeit herausfinden soll. Leider habe ich mit google nicht viel gefunden, das mir helfen konnte. Kann man grundsätzlich daraus schließen, dass ein Code, welcher zwei for-Schleifen hat immer O(n^2) ist?!

Würde mich wirklich freuen, wenn mir jemand ein Paar Beispiele machen könnte mit den entsprechenden Größenordnungen.

Wie sieht es mit Rekursionen aus? Welche Laufzeit haben die? Hat jemand auch Beispiele über Rekursion?

Bin wirklich am Verzweifeln. Ich hoffe, jemand kann mir helfen.

Viele Grüße
Nesli

 

[XHelp]

Kann man grundsätzlich daraus schließen, dass ein Code, welcher zwei for-Schleifen hat immer O(n^2) ist?!

Nein, O(n^2) wäre:

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

Wenn sich die Bedingung ändert, ändert sich auch die Laufzeit.

Wie sieht es mit Rekursionen aus? Welche Laufzeit haben die?

Das kommt auch drauf an was du da machst. Wenn du sowas wie

boolean rek(int n) {
  if (n<=0) {
    return true;
  }
  return rek(n-1);
}

hast, dann ist die Laufzeit O(n);
Wenn du aber

boolean rek(int n) {
  if (n==0) {
    return true;
  }
  return rek(n/2);
}

hast, dann ist die Laufzeit O(log(n))

Wie schon erwähnt: es gibt keine Laufzeit für "eine allgemeinte Schleife" oder "eine allgemeinte Rekursion". Du musst schon gucken, was in dem Code passiert.

 

[Nesli]

Danke für die schnelle Antwort. Wie sieht es mir folgendem Code aus:

for(int i=0; i < 1000*n;i++ ){
    for(int j = 0; j < 1000; j++) {
      int sum = sum + 1;
    }

}

Ich würde sagen, dass die Laufzeit O(n) ist, ist das Korrekt?

LG
Nesli

 

[XHelp]

Ja, die Laufzeit ist ja eigentlich O(1000*1000*n), aber die Konstanten fliegen weg.

 

[Nesli]

Danke, dann sieht es aus, dass ich es fast vestanden habe. Was mache ich wenn ich sowas habe:

public int f12(n) {
  if(n >=4 ) {
    return f12(sqrt(n))
  } else {
    return 1;
  }
}

Wie beeinflusst sqrt(n) die Laufzeit?

Ich persönlich würde sagen, dass die Laufzeit bei O(log n) liegt, oder liege ich falsch?

Vielen Dank im Voraus.

LG
Nesli

 

[XHelp]

Generell ist die Aussage nicht falsch. Das besagt ja, dass es nicht schneller als log(n) wächst.
Aber falls ich mich nicht täusche, wird da irgendwas mit log(ln(... rauskommen.

 

[Mambong]

Für den Worst-Case ist das O(sqrt(n))

 

[Mambong]

Aeh, vergiss meinen Post ...