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
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