Algorithmen und Datenstrukturen · Senior · Frage 44 von 75
Welche Zeitkomplexität hat der naive Aufbau eines Suffix-Arrays durch Sortieren aller Suffixe?
- 1O(n), da Suffixe schon geordnet sind
- 2O(n² log n): ein Suffixvergleich kostet O(n)
- 3O(n log n), wie beim Sortieren von Zahlen
Antwort zeigen
Richtige Antwort: O(n² log n): ein Suffixvergleich kostet O(n)
Erklärung
Es gibt n Suffixe und n log n Vergleiche, von denen jeder O(n) Zeichen lesen kann. Prefix Doubling bringt es auf O(n log n), SA-IS auf O(n). Suffix-Arrays beantworten Teilstring-Abfragen per binärer Suche.