SuffixArray => SuffixBaum

11.02.2012, 23:05	Auf diesen Beitrag antworten »
akvarel	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?


12.02.2012, 12:53	Auf diesen Beitrag antworten »
Karlito	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:...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

Verwandte Themen