Алгоритми та структури даних · Senior · Запитання 44 з 75
Яка часова складність наївної побудови суфіксного масиву сортуванням усіх суфіксів?
- 1O(n), бо суфікси вже природно впорядковані
- ✓Правильна відповідь: O(n² log n): порівняння суфіксів - O(n)
- 3O(n log n), як сортування чисел
Пояснення
Суфіксів n, порівнянь n log n, і кожне може читати O(n) символів. Подвоєння префіксів дає O(n log n), а SA-IS - O(n). Суфіксні масиви відповідають на запити про підрядки бінарним пошуком.