O notation, Laufzeitanaylse

Question

Frage:

Hallo, ich habe letztes Jahr eine Prüfung geschrieben und da musste man die Laufzeit angeben des jeweiligen Programmes.

Mein Professor hat mir auch dir Lösungen hingeschrieben, aber leider kann ich bei paar Sachen die Dinge noch nicht ganz Nachvollziehen.

def f(n):
   x=0
   y=n
   while y>0:
      for i in range(y):
         x+=1
      y =y//2
   return x
#Lösung 0(n)

def f(n):
   if n<=1:
      return 1
else:
   x=0
   for i in range(n):
      x=0
   return f(n//2)+f(n//2)
#Lösung O(n logn)

def f(n):
   if n<=3:
      return 4
   else:
      z=0
      y=2
   while z<n:
      for i in range(z):
         y=f(3)
       z+=1
   return z
#Lösung O(n^2)

Für jede Hilfe wäre ich sehr Dankbar :)

Answer 1

Hallo, ich rechne dir das mal exemplarisch am ersten Code vor. Wichtig dabei ist, dass du dir die Schleifen genau angucken musst und auch hier beachten musst, dass die Iterationsgrenze \(y\) der for-Schleife nach jedem while-Block in etwa halbiert wird. Das ist im Grunde alles, was du zur Laufzeitabschätzung (nachoben) brauchst. Zunächst mal ein paar Beispiele:

Für \(n=7\) hat man y-Werte: \(7,3,1\) mit \(3\) Durchläufen.

Für \(n=25\) hat man y-Werte: \(25,12,6,3,1\) mit \(5\) Durchläufen.

Allgemein sind das also \(\alpha:=\left \lfloor{\log_2(n)}\right \rfloor+1\) Durchläufe (also endlich viele) der while-Schleife für alle \(n\in \mathbb{N}_{\geq 1}\).

Dann siehst du bei etwas längerem Hinsehen, dass \(y\) im \(k\)-tem Schleifendurchlauf der while-Schleife genau \(\left \lfloor{\frac{n}{2^k}}\right \rfloor\) entspricht, was nach dem Code die Iterationsgrenze der for-Schleife ist. Das kannst du auch in den obigen Beispielen gut einsehen. In jeder Iteration der for-Schleife dieses Programmes werden immer konstant \(c\) viele Operationen getätigt.

Jetzt wird die Laufzeitabschätzung durchgeführt:

\(T(n)=\underbrace{\sum\limits_{k=0}^{\alpha}\underbrace{\sum\limits_{i=1}^{\left \lfloor{\frac{n}{2^k}}\right \rfloor} c}_{\text{Innere for-Schleife}}}_{\text{while-Schleife}}=\sum\limits_{k=0}^{\alpha}\Big(c\cdot \sum\limits_{i=1}^{\left \lfloor{\frac{n}{2^k}}\right \rfloor} 1\Big)=\sum\limits_{k=0}^{\alpha} c\cdot \left \lfloor{\frac{n}{2^k}}\right \rfloor\\\leq c\cdot \sum\limits_{k=0}^{\alpha} \frac{n}{2^k}=c\cdot n\cdot \sum\limits_{k=0}^{\alpha} \frac{1}{2^k}\leq c\cdot n\cdot \sum\limits_{k=0}^{\infty} \frac{1}{2^k}\stackrel{\text{geometrische Reihe}}{=}c\cdot n\cdot 2\in \mathcal{O}(n)\).

Zum zweiten Code lass dir gesagt sein, dass es sich um einen rekursiven Algorithmus handelt, was daran zu sehen ist, dass deine Funktion innerhalb des Codes nochmal aufgerufen wird. Speziell für solche rekursiven Algorithmen gibt es Laufzeitabschätzungen (-> siehe Master Theorem: https://de.wikipedia.org/wiki/Master-Theorem oder eure Bezeichnung dafür in der Veranstaltung).

Bei Fragen gerne schreiben. :-)

Comments

Achso. Beachte, dass ich bei der Summierung für die innere for-Schleife bei \(i=1\) statt bei \(i=0\) anfange zu zählen. Das hat aber keine Auswirkungen auf die Anzahlen der Durchläufe; Indexverschiebung.

Sicher, dass bei deinem dritten Code (unten) z innerhalb der for-Schleife inkrementiert werden soll?