4551
правка
Сжатый суффиксный массив: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 54: | Строка 54: | ||
'''Теорема 2 (Гросси и Виттер, 2005 [3]). Сжатый суффиксный массив Гросси и Виттера поддерживает извлечение A[i] за время | '''Теорема 2 (Гросси и Виттер, 2005 [3]). Сжатый суффиксный массив Гросси и Виттера поддерживает извлечение A[i] либо за время <math>O(log \; log \; n)</math> с использованием <math>n \; log \; \sigma \; log \; log \; n + O(n \; log \; log \; \sigma)</math> бит памяти, либо за время <math>O(log^{\epsilon} \; n)</math> с использованием <math>\frac{1}{\epsilon} \; n \; log \; \sigma + O(n \; log \; \; log \; \sigma)</math> бит памяти для любого <math>0 < \epsilon < 1</math>.''' | ||
