Laufzeitkomplexität

Bachelor Algorithmen und Datenstrukturen
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Laufzeitkomplexität
Hey Leute,

ich hab mal eine Frage betreffs Laufzeitkomplexität von for-Schleifen.

Wenn ich jetzt 2 Vorschleifen hab, die bis n laufen und in den beiden Vorschleifen dann eine Anweisung hab, die O(n) hat, hab ich dann als gesamte Laufzeit O(n^3)?
Werden die Vorschleifen addiert oder multipliziert? Wann haben Vorschleifen O(logn)?

Bitte um Hilfe!!! :slight_smile:

Danke

3

also nehmen wir mal an das sieht so aus: //Vergiss meinen Eintrag ---- Der von MalteM drunter ist besser----


for(int i = 0; i < n; i++){   //O(n) * (O(n) + O(n^2))

     //something in O(n)

    for(int j = 0; j < n; j++){     //O(n) * O(n)
     //something in O(n)
   }
}

Dann sollte dein O(n^3) richtig sein denk ich, da ja die O-Kalkül Additions Regel gilt

Ich weiß zwar nicht ob die Regel immer gilt, aber Schleifen haben O(log(n)), wenn i multipliziert wird

beispiel:


for(int i = 0; i < n; i *= 2){   //O(log(n))

     //something in O(1)

}

zusatz:
Generell gilt bei Schleifen - wenn sequentiell, dann addieren, sonst multiplizieren =>
Schleifen werden nur dann multipliziert wenn die eine Schleife in der anderen steckt.

Beispiel



//Gesamtaufwand O(n^2)
for(int i = 0; i < n; i++){   //O(n) *  O(n) 

    for(int j = 0; j < n; j++){     //O(n) 
     //something in O(1)
   }
}

********************************************************************************
//Gesamtaufwand O(n)
for(int i = 0; i < n; i++){   //O(n)
//something in O(1)
}

for(int j = 0; j < n; j++){     //O(n) 
     //something in O(1)
   }
4

for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // O(n) } } läuft in O(n³), ja.

for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { // O(n) } } auch (hint: kleiner Gauß für Gesamtanzahl der Durchläufe der inneren Schleife).

for (int i = 1; i < n; i *= 2) { // O(1) } läuft in O(log₂ n).

for (int i = 1; i < n; i *= 2) { // O(n) } läuft in O(n log₂ n).

Grundsätzlich kann man die Komplexitäten multiplizieren, wenn sie einfach von n abhängen. Wenn sie von Laufvariablen abhängen, sieht das ein bisschen anders aus:

for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // O(j) } } läuft auch in O(n³) (wieder kleiner Gauß, diesmal aber nicht für die Anzahl der Durchläufe, sondern die Komplexität der inneren Schleife).

for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { // O(j) } } auch (kleiner Gauß in der inneren Schleife (läuft insgesamt in O(i²)), dann ähnliche Formel für Summe von Quadraten in der äußeren).

for (int i = 1; i < n; i *= 2) { // O(i) } läuft aber nicht in O(log₂ n) oder O(n log₂ n), sondern in O(n) (hint: geometrische Reihe).
Und noch ein fieser:

for (int i = 0; i < n; i *= 2) { // O(i) } terminiert nicht.