Subato

Resource Files

Code-Komplexität

Gegeben sind ein paar (Pseudo-)Code-Stücke. Schätzen Sie jeweils die zugehörige Komplexitätsklasse ab und begründen Sie.

Tipp: Gehen Sie immer bottom-up vor. Bestimmen Sie zunächst die Komplexität der inneren Schleifenteile, dann die der äußeren.

  • Leiten Sie für diese Schleife die Worst Case Komplexität her. Gezählt wird die Anzahl der Feldzugriffe. Gegeben sei ein Integer-Array a der Länge $n>20$.
result = 0;
for (int i=0; i<n/2; i += 5) {
  for (int j=0; j<10; ++j) {
     result += a[i+j];
  }
}
return result;
  • Leiten Sie für diese Schleife Best Case und Worst Case her. Gezählt wird die Anzahl der Feldzugriffe. Gegeben sei ein Integer-Array a der Länge $n$.  Nehmen Sie an dass foo(n) die Komplexität $\Theta(n)$ besitzt.
for (int x : a) {
  for (int i=0; a[i]!=x; ++i) {
    foo(i);
  }
}
  • Leiten Sie für diese Schleife die Worst Case Komplexität her. Gezählt wird die Anzahl der Feldzugriffe.
result = 0;
for (int i=0; i<a.length; ++i) {
  for (int j=i; j>0; j/=2) {
    result += a[j];
  }
}
return result;
  • Leiten Sie den Aufwand der folgenden rekursiven Funktion her. Gezählt werden Additionen und Subtraktionen (jeweils Kosten 1).
function bar(int n):
  if (n <= 0)
    return 0
  else
    return n + bar(n-2)


You are not logged in and therefore you cannot submit a solution.