Ergebnis 1 bis 3 von 3

Thema: Zeitkomplexität bestimmen

  1. #1
    Suchtspielmacher (ehm.) Avatar von werner
    Registriert seit
    Jul 2014
    Ort
    Mannheim
    Beiträge
    704

    Zeitkomplexität bestimmen

    Moin,

    ich muss ja sagen, dass ich generell Das mit den O(n) 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):

    Code (Python):
    1. def findNext(n, position_list)
    2.     for pos in range(1, n+1):
    3.         if pos not in position_list:
    4.             return pos
    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(n), 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

  2. #2
    Mitglied
    Registriert seit
    Jul 2013
    Beiträge
    365
    ngb:news Artikel
    1

    Re: Zeitkomplexität bestimmen

    Angenommen position_list ist eine Liste. Dann muss pos not in position_list die komplette Liste durchgehen, um sicherzustellen dass pos dort nicht enthalten ist. Die Länge der Liste ist <= n, also maximal n Schritte. Damit hat schon der Ausdruck pos not in position_list die Laufzeit O(n) - 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(n) 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. x in set und x not in set lassen sich in O(log n) implementieren. Das funktioniert z.B. mit der klassischen "Telefonbuch-Suche" / Binäre Suche 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
    Für diesen Beitrag bedanken sich BurnerR, MingsPing, werner

  3. #3
    Suchtspielmacher (ehm.)

    (Threadstarter)

    Avatar von werner
    Registriert seit
    Jul 2014
    Ort
    Mannheim
    Beiträge
    704

    Re: Zeitkomplexität bestimmen

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

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •