Laufzeitkomplexität mit O Notation
Verfasst: Montag 27. Juni 2022, 14:06
Guten Tag zusammen.
Ich habe in wenigen Wochen eine Klausur über das Thema Algorithmen und Datenstrukturen.
Einer unserer Aufgaben ist es die Laufzeitkomplexität von Funktionen und allgemeinen Programmen zu bestimmen. Da die Vorlesung dieses Semester allerdings nicht
angeboten wird, bin ich hier auf mich alleine gestellt und habe nur die Folien unseres Professors zur Hand. Ich habe hier einige Aufgaben, bei denen ich mir nicht sicher bin, wie ich die Laufzeitkomplexität bestimmen soll. Gibt es hier eventuell jemand, der mir hierbei helfen kann? Die Programme sind recht simple gehalten.
Einige Beispiele wären:
def variante1( liste):
maxi = 0
for i in liste:
if i > maxi:
maxi = 1
return maxi
--> hier hätte ich die Laufzeitkomplexität auf O(n) festgelegt, da die Schleife abhängig von der Länge der Liste n mal durchlaufen wird
def variante2(liste):
if len(liste)==1:
return liste[0]
maxi = variante2(liste[1:])
if liste[0] > maxi:
return liste[0]
else:
return maxi
--> hier bin ich mir zum Beispiel nicht mehr ganz sicher, welche Laufzeitkomplexität der Aufruf der Funktion len() hat. Hier hätte ich O(1) bestimmt
def variante3(liste, counter=0):
index = len(liste)-counter-1
if index==0:
return liste[0]
maxi = variante3(liste, counter+1)
if liste[index] > maxi:
return liste[index]
else:
return maxi
--> ???
Ich bin für jegliche Hilfe der dankbar
Viele Grüße
Ich habe in wenigen Wochen eine Klausur über das Thema Algorithmen und Datenstrukturen.
Einer unserer Aufgaben ist es die Laufzeitkomplexität von Funktionen und allgemeinen Programmen zu bestimmen. Da die Vorlesung dieses Semester allerdings nicht
angeboten wird, bin ich hier auf mich alleine gestellt und habe nur die Folien unseres Professors zur Hand. Ich habe hier einige Aufgaben, bei denen ich mir nicht sicher bin, wie ich die Laufzeitkomplexität bestimmen soll. Gibt es hier eventuell jemand, der mir hierbei helfen kann? Die Programme sind recht simple gehalten.
Einige Beispiele wären:
def variante1( liste):
maxi = 0
for i in liste:
if i > maxi:
maxi = 1
return maxi
--> hier hätte ich die Laufzeitkomplexität auf O(n) festgelegt, da die Schleife abhängig von der Länge der Liste n mal durchlaufen wird
def variante2(liste):
if len(liste)==1:
return liste[0]
maxi = variante2(liste[1:])
if liste[0] > maxi:
return liste[0]
else:
return maxi
--> hier bin ich mir zum Beispiel nicht mehr ganz sicher, welche Laufzeitkomplexität der Aufruf der Funktion len() hat. Hier hätte ich O(1) bestimmt
def variante3(liste, counter=0):
index = len(liste)-counter-1
if index==0:
return liste[0]
maxi = variante3(liste, counter+1)
if liste[index] > maxi:
return liste[index]
else:
return maxi
--> ???
Ich bin für jegliche Hilfe der dankbar
Viele Grüße