Datenstrukturen: Laufzeiten / Time Complexity

In den letzten Beiträgen wurden die wichtigsten Datenstrukturen vorgestellt. Nun sollen die Laufzeitkomplexitäten aller Datenstrukturen behandelt werden.

Unter einer Laufzeitkomplexität (engl. time complexity) versteht man, wie lange es in Abhängigkeit einer Eingabemenge n dauert, ein gegebenes Problem zu lösen. Diese Laufzeitkomplexität ist auch bekannt als Groß-O-Notation oder Landau-Notation [1].
Weiterhin unterscheidet man zwischen drei Fällen: bester Fall (best-case), durchschnittlicher Fall (average-case) und den schlechtesten Fall (worst-case).

Beispiel

bester Fall: Das gesuchte Objekt befindet sich an erster Stelle im Array. Die Schleife kann sofort abgebrochen werden.

durchschnittlicher Fall: Das gesuchte Objekt befindet sich irgendwo im Array. Es ist aber nicht der Anfang und auch nicht das Ende.

schlechtester Fall: Das gesuchte Objekt ist an der letzten Stelle. Das vollständige Array muss durchlaufen werden.

Wenn es um Laufzeitabschätzungen geht, dann wird in der Regel der worst-case betrachtet.
Im folgenden werden für alle behandelten Datenstrukturen die Operationen: Suchen, Einfügen und Entfernen für den worst-case betrachtet.

Datenstruktur	suchen	einfügen	entfernen
Das Array	O(n)	O(1)	O(1)
Das 2D-Array	O(n²)	O(1)	O(1)
Die Liste	O(n)	O(n)	O(n)
Der Stack	O(n)	O(1)	O(1)
Die Queue	O(n)	O(1)	O(1)
Das Set	O(n)	O(n)	O(n)
Die Map	O(n)	O(n)	O(n)
Der Binärbaum	O(log(n))	O(log(n))	O(log(n))
Der Graph	O(n)	O(n)	O(n)

Tabelle: Überblick über die Laufzeiten

Die Laufzeiten im Detail

• Das Array
  Suchen: Im schlimmsten Fall muss das vollständige Array durchlaufen werden, O(n)
  Einfügen und Entfernen sind nicht Möglich, da Arrays nicht dynamisch sind. Man kann nur Elemente per direkten Zugriff manipulieren: O(1)

• Das 2D-Array
  Suchen: Um ein 2D-Array zu durchlaufen ist eine verschachtelte Schleife notwendig. Die Laufzeit lautet: O(n)*O(n)=O(n²)
  Einfügen und Entfernen sind wie bei einem Array nicht möglich.

• Die Liste
  Suchen: Ein Objekt muss in der Liste erst gefunden werden. Im schlimmsten Fall ist es das letzte Objekt O(n)
  Einfügen: An einer beliebigen Stelle O(n), da die Liste erst bis zu diesem Element durchlaufen werden muss.
  Entfernen: Hier muss die Liste im schlimmsten Fall bis zum Ende durchlaufen werden bevor das Objekt gelöscht wird O(n)

• Der Stack
  Suchen: Für das Suchen eines Objekts muss man den Stack durchlaufen. Genauso wie bei einer Liste hat dies eine Laufzeit von O(n). Allerdings ist nur das Entfernen des letzten Objektes möglich.
  Einfügen: Es wird immer ein Objekt an das Listenende eingefügt. Die Laufzeit beträgt O(1) und nicht O(n), da man den Stack zuvor nicht durchlaufen muss.
  Entfernen: Analog zu Einfügen, nur dass das Objekt vom Listenende entfernt wird O(1)

• Die Queue
  Eine Queue ist das Gegenstück eines Stacks. Hier sind die Laufzeiten mit denen eines Stacks identisch.

• Das Set
  Suchen: Um ein Objekt zu finden, muss ein Iterator im schlimmsten Fall das vollständige Set durchlaufen. Die Laufzeit lautet: O(n).
  Einfügen: Beim einfügen wird das Set überprüft, ob dieses Objekt bereits existiert. Daher lautet die Laufzeit: O(n)
  Entfernen: Um ein Objekt zu entfernen, muss der Iterator dieses erst im Set finden. Das dauert O(n) Zeit.

• Die Map
  Suchen: Es muss definitiv ein Iterator benutzt werden, um an einen bestimmten Key zu kommen. Wo sich dieser Key befindet lässt sich nicht vorhersagen, da eine Map keine Indizes hat. O(n)
  Einfügen: Beim Einfügen wird zunächst ein Hashwert berechnet und auf eventuelle Kollisionen in der Map überprüft. Es wird also auf die vollständige Map zugegriffen. O(n)
  Entfernen: Beim Entfernen muss zunächst der richtige Key gefunden werden, was eine Iteration unumgänglich macht. O(n)

• Der Binärbaum
  Suchen: Nach jeder Ebene werden die Anzahl der Indizes halbiert. Die Laufzeit lautet O(log(n)) bevor ein Objekt gefunden werden kann.
  Einfügen: Beim einfügen eines Objektes wird zunächst der Index ermittelt, wohin eingefügt wird. Dieser Index muss gefunden werden. O(log(n))
  Entfernen: Analog zum einfügen. O(log(n))

• Der Graph
  Wichtig: Es kommt darauf an, mit welchen Datenstrukturen man Graphen implementiert hat. Für den Fall, dass eine Map benutzt wird, gelten die Laufzeiten einer Map. Zusätzlich kommt die Laufzeit der Datenstruktur hinzu, welche als Values genommen wird.
  Suchen: Wird nur nach einem Knoten gesucht, wäre die Laufzeit: O(n). Sucht man nach einer Verbindung, dann kommt noch die Such-Laufzeit eines Set hinzu. Insgesamt also: O(n) + O(n) = 2*O(n) = O(n)
  Einfügen: Beim einfügen eines Knotens gilt die Einfüge-Laufzeit einer Map O(n) zusammen mit der Einfüge-Laufzeit eines Set O(n). Insgesamt: O(n)
  Entfernen: Wird der Knoten entfernt, dann lautet die Laufzeit O(n). Wird aber eine Kante gelöscht, dann wird auch hier die Entfernen-Laufzeit des Sets hinzukommen O(n). Insgesamt: O(n)

Quellen:
[1] http://www.iitk.ac.in/esc101/2009Jan/lecturenotes/timecomplexity/TimeComplexity_using_Big_O.pdf
[2] https://www.bigocheatsheet.com/