Informatiker Board | Druckvorschau: SuffixArray => SuffixBaum

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Praktische Informatik (http://www.informatikerboard.de/board/board.php?boardid=6)
---- Algorithmen (http://www.informatikerboard.de/board/board.php?boardid=17)
----- SuffixArray => SuffixBaum (http://www.informatikerboard.de/board/thread.php?threadid=1154)

Geschrieben von akvarel am 11.02.2012 um 23:05:

SuffixArray => SuffixBaum

Meine Frage:
Hallo!
Um einen Suffixbaum in einen Suffixarray umzuwandeln, muss man ja die Tiefen-Suche anwenden. Tiefen-Suche braucht O(|E|+|V|) Zeit. E-Kanten,V-Knoten.
Warum dann finde ich immer im Internet, dass die Laufzeit um einen SB in einen SA umzuwandeln mittels DFS nur O(|V|) beträgt? Übrigens, das hat auch mein Tutor gesagt.

Meine Ideen:
Darf man Kanten also einfach weglassen?

Geschrieben von Karlito am 12.02.2012 um 12:53:

RE: SuffixArray => SuffixBaum

Hi,

die Laufzeitabschätzung, dass die Tierfensuche durch $[latex]f \in \mathcal{O}(|E|+|V|)[/latex]$ begrenzt ist, gilt für allgemeine Graphen. Hier Können Mehrfachkanten auftreten und diese müssen auch untersucht werden. Weiterhin gilt es wohl auch noch Hypergraphen zu betrachten. S. http://de.wikipedia.org/wiki/Diskussion:Tiefensuche#O_-_Notation_f.C3.BCr_Tiefensuche

Da es sich bereits um einen Baum Handelt, führt jeder Knoten nur zu einem Nachfolgeknoten.Wahrscheinlich wäre hier genauer $[latex]f \in \mathcal{O}(2|V|-1)[/latex]$ , im allgemeinen lässt man jedoch dann die Faktoren und Konstanten weg, da diese unerheblich für die Laufzeitbetrachtung sind.

VG,

Karlito