 SuffixArray => SuffixBaum |
akvarel
Grünschnabel
Dabei seit: 11.02.2012
Beiträge: 1
 |
|
| 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?
|
|
11.02.2012 23:05 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
| RE: SuffixArray => SuffixBaum |
|
Hi,
die Laufzeitabschätzung, dass die Tierfensuche durch ![[latex]f \in \mathcal{O}(|E|+|V|)[/latex]](http://www.matheboard.de/latex2png/latex2png.php?f \in \mathcal{O}(|E|+|V|)) 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:...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]](http://www.matheboard.de/latex2png/latex2png.php?f \in \mathcal{O}(2|V|-1)) , im allgemeinen lässt man jedoch dann die Faktoren und Konstanten weg, da diese unerheblich für die Laufzeitbetrachtung sind.
VG,
Karlito
|
|
|
12.02.2012 12:53 |
|
|
|
