Algorytmy i struktury danych · Senior · Pytanie 44 z 75
Jaka jest złożoność czasowa naiwnego budowania tablicy sufiksowej przez sortowanie wszystkich sufiksów?
- 1O(n), bo sufiksy są już uporządkowane
- ✓Poprawna odpowiedź: O(n² log n), bo porównanie sufiksów kosztuje O(n)
- 3O(n log n), tak jak sortowanie liczb
Wyjaśnienie
Sufiksów jest n, porównań n log n, a każde może czytać O(n) znaków. Podwajanie prefiksów daje O(n log n), a SA-IS O(n). Tablice sufiksowe odpowiadają na zapytania o podnapisy wyszukiwaniem binarnym.