• Hallo liebe Userinnen und User,

    nach bereits längeren Planungen und Vorbereitungen sind wir nun von vBulletin auf Xenforo umgestiegen. Die Umstellung musste leider aufgrund der Serverprobleme der letzten Tage notgedrungen vorverlegt werden. Das neue Forum ist soweit voll funktionsfähig, allerdings sind noch nicht alle der gewohnten Funktionen vorhanden. Nach Möglichkeit werden wir sie in den nächsten Wochen nachrüsten. Dafür sollte es nun einige der Probleme lösen, die wir in den letzten Tagen, Wochen und Monaten hatten. Auch der Server ist nun potenter als bei unserem alten Hoster, wodurch wir nun langfristig den Tank mit Bytes vollgetankt haben.

    Anfangs mag die neue Boardsoftware etwas ungewohnt sein, aber man findet sich recht schnell ein. Wir wissen, dass ihr alle Gewohnheitstiere seid, aber gebt dem neuen Board eine Chance.
    Sollte etwas der neuen oder auch gewohnten Funktionen unklar sein, könnt ihr den "Wo issn da der Button zu"-Thread im Feedback nutzen. Bugs meldet ihr bitte im Bugtracker, es wird sicher welche geben die uns noch nicht aufgefallen sind. Ich werde das dann versuchen, halbwegs im Startbeitrag übersichtlich zu halten, was an Arbeit noch aussteht.

    Neu ist, dass die Boardsoftware deutlich besser für Mobiltelefone und diverse Endgeräte geeignet ist und nun auch im mobilen Style alle Funktionen verfügbar sind. Am Desktop findet ihr oben rechts sowohl den Umschalter zwischen hellem und dunklem Style. Am Handy ist der Hell-/Dunkelschalter am Ende der Seite. Damit sollte zukünftig jeder sein Board so konfigurieren können, wie es ihm am liebsten ist.


    Die restlichen Funktionen sollten eigentlich soweit wie gewohnt funktionieren. Einfach mal ein wenig damit spielen oder bei Unklarheiten im Thread nachfragen. Viel Spaß im ngb 2.0.

Zeitkomplexität bestimmen

werner

Suchtspielmacher (ehm.)

Registriert
20 Juli 2014
Beiträge
743
Ort
Mannheim
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):

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

Rakorium-M

NGBler

Registriert
14 Juli 2013
Beiträge
413
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(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. [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 "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
 

werner

Suchtspielmacher (ehm.)

Registriert
20 Juli 2014
Beiträge
743
Ort
Mannheim
  • Thread Starter Thread Starter
  • #3
Super, das ging ja fix. Deine erklärung für log n hat mir auch geholfen :)
 
Oben