Komplexität und Schleifen

[Ceppi]

Hallo,

zwar hat meine Frage nicht zwingend mit Java zu tun, dafür aber mit Algorithmen. Wie berechnet man die Anzahl von Schleifendurchläufen bei folgendem Code, um anschließend die Komplexitätsklasse zu bestimmen:

// n>3
for(int i=2; i<=n-1; i++) {
  for(int j=-1; j<=3*i+1; j++) {
    // Inhalt der inneren Schleife, wie oft durchlaufen?
  }
}

Mir fällt dazu vor allem nicht ein, wie ich die Verknüpfung von Laufvariable der äußeren Schleife mit Abbruchbedingung der inneren Schleife in meine Rechnung einbaue.

Gruß
Ceppi

 

[ADA&QS]

Sobald man das Prinzip verstanden hat, ist bei dieser Aufgabe recht einfach.
Die ausser Schleife geht 1 bis n dabei wird jeweils die innere Schleife ausgeführt wobei dies von aktuelle Wert von i abhängt. Nehmen wir den Grenzwert n-1 als Wert für i an so setzten wir das in die innere Schleife ein 3(n-1)+1 so gibt sich eine grenz von 3n-2 also n. Um die Abschätzung nach 0-Notation zu erhalten (n-1)*(3n-2) liegt also in n²

 

[Ceppi]

Nochmal nachvollzogen:

• Die äußere Schleife läuft n-2 mal. O
• Die innere Schleife läuft maximal 3*i+3 mal 0 >> 3*(n-2)+3 = 3n-3 mal
• (n-2)*(3n-3) = 3n^2-9n O(n^2)

Damit wäre der Komplexitätsklasse genüge getan. In meiner Aufgabe ist aber die genaue Anzahl an Schleifendurchläufen gefragt...

Trotzdem schonmal Danke für deine Hilfe.

 

[ADA&QS]

Als kleiner Hinweis i = 3 bis n und aufsummieren.