Laufzeitkomplexität mit O Notation

[deft22]

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

[__deets__]

Die Komplexitaet von len kannst du ja prinzipiell nachschlagen, oder ermitteln. Indem du zB mit dem timeit Modul misst, ob es einen Laufzeitunterschied zwischen einer 1-elementigen und zB einer 10_000_000-elementigen Liste gibt. Und ganz allegmein mal ueberlegst, ob eine Liste ihre Laenge kennen kann, ohne dafuer ueber ihre Elemente wandern zu muessen mit for, was ja dein Argument fuer O(n) war.

Und dann zur variante2: wenn du dir mal die Aufrufkette dieser (rekursiven) Implementierung anschaust, dann solltest du auf die Komplexitaet kommen.

Gleiches gilt fuer die letzte Variante. Auch da einfach mal aufschreiben, was da nacheinander aufgerufen wird.

[__blackjack__]

@deft22: Beim ersten ist ziemlich sicher ein Tippfehler oder ist das OCR von einem gedruckten Text?

Ich würde hier erst einmal die Voraussetzungen formulieren unter denen die Aussagen dann getroffen werden. Also mindestens mal für die verwendete Implementierung von Listen oder zumindest die ”weich” garantierten Obergrenzen von CPython die im Python.org-Wiki stehen, wenn man sich nicht die konkrete Implementierung anschauen möchte: https://wiki.python.org/moin/TimeComplexity

Ohne diese Seite kann man die Komplexität von `len()` auf Listen nämlich gar nicht sicher sagen, das könnte sowohl 1 als auch n sein, je nach dem an welchem (sinnvollen) Ende die zugrundeliegende Implementierung liegt. Bei `variante2()` ist eine Operation dabei die auch sowohl 1 als auch n sein kann. Und bei `variante3()` ebenfalls.