TU Wien:Algorithmen und Datenstrukturen 2 VO (Raidl)/Laufzeiten und co

Laufzeiten Textsuche

Algorithmus	Muster Angelegt	Vergleiche	Laufzeit
Naive Suche	N-M+1	$\Theta (N*M)$	$o(N*M)$
Knuth-Morris-Pratt			$O(N+M)$
Boyer-Moore			$O(N+M)$\\ $o(N+M)$ **

** Falls nur die last Verschiebung implementiert wird

Laufzeiten Rest

Randomisiertes Quicksort

$o(n*log(n))$

Primzahltests

Naiver Primzahltest

$o({\sqrt {(}}n))$

Miller-Rabin

$o(s*k^{3})$

s...Anzahl der Tests

k...Anzahl der Bits der Primzahl

Skipliste

• (Alle Skiplisten) Suche:O(log(n))
• (Random) Einfügen: O(log(n)) - Löschen: O(log(n))
• (Perfekte) Einfügen: O(log(n)+n)==O(n)- Löschen: O(log(n)+n)==O(n)

BEST CASE Szenarien

• Suchen (Alle Skiplisten): Erstes Element wird gesucht - Höhe+2
• (Random) Einfügen: Höhe+2 - Löschen: Höhe+2
• (Perfekte) Einfügen: $\Omega (log(n)$ - Löschen: $\Omega (log(n))$ ... weil nicht reorganisiert werden muss

Geometrische Algos

SSS...Scanline Status Struktur (Menge aktiver Segmente. geordnet nach der y-Koordinate des Schnittpunkts der aktuellen Scanline)
Ereignisstypen:

• Segmentanfang
• Segmentende
• Schnittpunkt

k...Anzahl der Schnittpunkte

Iso-Orientierte Liniensegmente

$o(n*log(n)+R)$
R...Anzahl der sich Schneidenden Segmente

Allgemeine Liniensegment

$o((n+k)*log(n))$

2-Dimensionale Bereichssuche

$o({\sqrt {(}}n)+R)$

K-Dimensionale Bereichssuche

$o(k*n^{(1-1/k)}+R)$

Tries

Radix-Trie

• Einfügen/Suchen/Entfernen: $O(m)$

m ... Höhe des Baumes

Index-Trie

• Einfügen: $\Omega (m)$ und $O(m*|A|)$
• Suchen: $O(m)$
• Entfernen: $O(m*|A|)$

m ... länge des einzufügenden Wortes
A ... das verwendete Alphabet

Linked-Trie

• Suchen: $O(m*|A|)$

Packed-Trie

• Suchen: $O(m)$