Zeitkomplexität bestimmen

[werner]

Moin,

ich muss ja sagen, dass ich generell Das mit den O👎 und so weiter verstanden habe. Wann man allerdings dann O(n^2) oder O(n * log n) nutzt, das geht mir nicht ganz rein.

Nun habe ich ein Python-Code, welcher so aussieht (es geht um freie/leeren Positionen in einem Karton):

[src=python]def findNext(n, position_list)
for pos in range(1, n+1):
if pos not in position_list:
return pos[/src]

Dabei ist n die Anzahl der Positionen die es generell gibt, und position_list ist einer Liste aller belegten Positionen.
In dem Code suche ich die nächste freie Position (von unten aus).

Welche Komplexität besitzt diese Funktion denn?
Meine erste Idee war O👎, da man ja eine Schleife hat, die bis zu n-mal ausgeführt werden kann. Allerdings gibt es dann noch den Befehl "in" aus Python, der ja auch wieder die Liste durchsuchen muss.
Ich stehe also etwas auf dem Schlauch..

Hoffe mir kann jemand dabei helfen

LG
Markus

 

[Rakorium-M]

Angenommen position_list ist eine Liste. Dann muss [kw]pos not in position_list[/kw] die komplette Liste durchgehen, um sicherzustellen dass [kw]pos[/kw] dort nicht enthalten ist. Die Länge der Liste ist <= n, also maximal n Schritte. Damit hat schon der Ausdruck [kw]pos not in position_list[/kw] die Laufzeit O👎 - wenn er einmal läuft.
Jetzt führst du das aber in einer Schleife aus - im schlimmsten Fall wird der Ausdruck n mal ausgewertet. Also n * O👎 Schritte => O(n*n) => O(n^2), quadratische Laufzeit.

O(n*log n) kann man an deinem Beispiel auch ganz gut erklären. Angenommen du nutzt für position_list ein Set statt einer List. [kw]x in set[/kw] und [kw]x not in set[/kw] lassen sich in O(log n) implementieren. Das funktioniert z.B. mit der klassischen

You do not have permission to view link please Anmelden or Registrieren

oder eben den speziellen Set-Algorithmen (Binäre Bäume etc).
Dann führst du diesen Check wieder in einer Schleife aus: n * O(log n) Schritte => O(n* log n).

Hoffe das hilft dir weiter.
Gruß
Rakorium

 

[werner]

Super, das ging ja fix. Deine erklärung für log n hat mir auch geholfen