1632
правки
Изменения
Бор
,rollbackEdits.php mass rollback
Введем следующие обозначения:
*<tex>\Sigma</tex> {{---}} используемый алфавит;
*<tex>P = \{P_1,\ldots,P_k\} </tex> {{---}} набор строк над <tex>\Sigma</tex>, называемый словаремсловарём;
*<tex>n = \sum_{i=1}^{k}\limits |P_i|</tex> {{---}} сумма длин строк.
Построение занимает, очевидно, <tex>O(|P_1| + \ldots + |P_k|) = O(n)</tex> времени, так как поиск буквы, по которой нужно переходить, происходит за <tex>O(1)</tex>.
Поскольку на каждую вершину приходится <tex>O(1| \Sigma |)</tex> памяти, то использование памяти есть <tex>O(n| \Sigma |)</tex>.
===Суффиксный бор===
Несмотря на данные достоинства у реализации ассоциативного массива в виде бора есть следующие недостатки:
# Бор хранит строки или символы, а это значит, что у значения ключа будет ограничение на тип (строки, символы, либо числа, представленные как строки). Чтобы это исправить, научимся приводить любой тип данных к строке. Тогда сможем хранить любой вид данных в качестве ключа.
#Если реализовывать ассоциативный массив на обычном боре, а ключами будут являться строки, то будет использоваться слишком много памяти (возможен, например, вариант, когда у слов нет пересечений по префиксу, тогда бор будет использовать <tex>O(n| \Sigma |)</tex> памяти).
==См. также==
