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

Aus VoWi
Zur Navigation springen Zur Suche springen

Laufzeiten Textsuche[Bearbeiten | Quelltext bearbeiten]

Algorithmus Muster Angelegt Vergleiche Laufzeit
Naive Suche N-M+1
Knuth-Morris-Pratt
Boyer-Moore \\

**


** Falls nur die last Verschiebung implementiert wird

Laufzeiten Rest[Bearbeiten | Quelltext bearbeiten]

Randomisiertes Quicksort[Bearbeiten | Quelltext bearbeiten]

Primzahltests[Bearbeiten | Quelltext bearbeiten]

Naiver Primzahltest[Bearbeiten | Quelltext bearbeiten]

Miller-Rabin[Bearbeiten | Quelltext bearbeiten]

s...Anzahl der Tests

k...Anzahl der Bits der Primzahl

Skipliste[Bearbeiten | Quelltext bearbeiten]

  • (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: - Löschen: ... weil nicht reorganisiert werden muss

Geometrische Algos[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]


R...Anzahl der sich Schneidenden Segmente

Allgemeine Liniensegment[Bearbeiten | Quelltext bearbeiten]


2-Dimensionale Bereichssuche[Bearbeiten | Quelltext bearbeiten]


K-Dimensionale Bereichssuche[Bearbeiten | Quelltext bearbeiten]


Tries[Bearbeiten | Quelltext bearbeiten]

Radix-Trie[Bearbeiten | Quelltext bearbeiten]

  • Einfügen/Suchen/Entfernen:

m ... Höhe des Baumes

Index-Trie[Bearbeiten | Quelltext bearbeiten]

  • Einfügen: und
  • Suchen:
  • Entfernen:

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

Linked-Trie[Bearbeiten | Quelltext bearbeiten]

  • Suchen:

Packed-Trie[Bearbeiten | Quelltext bearbeiten]

  • Suchen: