Weitere asymptotische Laufzeitanalyse

Question

Aufgabe

Bestimmen Sie die asymptotische Laufzeit der folgenden Pseudocode-Fragmente als Θ- Notation in Abhängigkeit von n. Sie können davon ausgehen, dass n eine Potenz von 2 ist.

a)

int factor=0;
for(i=1; i <= n/8; i++) {
  int x=i;
  factor=factor*x;
  for(j=1; j <= n/4; j++)
    for(k=1; k < 97; k++)
      factor=factor/2;}

b)

for(i=0; i < 2n; i++) {
  int j=n;
  while (j >= 1)
    j=j/2;
}

c)

sum=0;
for (i=0; i<n; i++)
  for (j=0; j<nn; j++) for (k=0; k<j; k++) sum=sum+1;

d)

for (i=0; i<n; i++) {
  j=i;
  while (j>1) {
  j=j-3;
  }
}

Ansatz

a) Es wird immer durch n/4 geteilt, deswegen log (n). Da 3 For-Schleifen durchlaufen wird, n³. => LZ = Θ( n³ * log (n) )?

b) Selbe Begründung. Es wird bis zu einer gewissen Stelle j < n, immer j durch 2 geteilt. Wenn was durch 2 geteilt wird, ist es ein Signal für logarithmische Laufzeit: LZ = Θ (log(n))

c) Keine Ahnung..Summe spricht ja eigentlich für die Gauß'sche-Summenformel. Daher LZ = Θ (n²)

d) Hier wird immer etwas abgezogen, also über j-1 iteriert. Aufsummiert wäre auch hier die LZ = Θ (n²) ?

Answer 1

a)
Schleife 1 : n/8 Ausführungen
Schleife 2 : n/4 Ausführungen
Schleife 3 : unabhängig von n

Weil die Schleifen verschachtelt sind, gehen die Ausführungen multiplikativ ein (ist bei allen Aufgaben so).

LZ(n) = n/8 * n/4 = n^2/32 € O(n^2)

Stünden die Schleifen hintereinander, dann sähe es so aus

LZ(n) = n/8 + n/4 = 3n/8 € O(n)

b)

Schleife 1 : 2n Ausführungen
Schleife 2 : log_2(n) Ausführungen

LZ(n) = 2n * log_2(n) € O(n * log(n))

c)
Angenommen der Code lautet (Schreibfehler ?)

for(j=0, j < n; j++)
  for (k = 0, k < j; k++)
    sum = sum+1

 dann werden die beiden Schleifen n*(n+1)/2 mal durchlaufen.

Schleife 1 : n Ausführungen
Schleife 2 und 3 : n*(n+1)/2 Ausführungen

LZ(n) = n * n*(n+1)/2 € O(n^3)

Angenommen der Code lautet

for(j=0, j < n^2; j++)
  for (k = 0, k < j; k++)
    sum = sum+1

dann werden die beiden Schleifen n^2*(n^2+1)/2 mal durchlaufen.

Schleife 1 : n Ausführungen
Schleife 2 und 3 : n^2*(n^2+1)/2 Ausführungen

LZ(n) = n * n^2*(n^2+1)/2 € O(n^5)

d)
Schleife 1 : n Ausführungen
Schleife 2: n/3 Ausführungen

LZ(n) = n * n/3 = n^2/3 € O(n^2)