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>.
===Суффиксный бор===
====Достоинства====
Бор объединяет некоторые преимущества этих структур данных и позволяет одновременно делать следующие операции, которые каждая из структур не может делать по отдельности.
{| class="wikitable" style="width:10cm" border=1|+| || '''Бор''' || '''Дерево''' || '''Хеш-таблица'''|-|-align="center" bgcolor=#FFFFFF| ''Добавление элемента в ассоциативный массив за '' | align="center" style="background: #ddffdd;" | <tex>O(|S|)</tex> (дерево выполняет данную операцию за | align="center" style="background: #ffdddd;" |<tex>O(|S|\log k)</tex>| align="center" style="background: #ddffdd;" | <tex>O(|S|).</tex>|-align="center" bgcolor=#FFFFFF| ''Получение всех ключей в отсортированном порядке за '' | align="center" style="background: #ddffdd;" | <tex>O(k)</tex> | align="center" style="background: #ddffdd;" | <tex>O(хеш-таблица выполняет данную операцию за k)</tex> | align="center" style="background: #ffdddd;" | <tex>O(k\log k)</tex>).|}
====Недостатки====
Несмотря на данные достоинства у реализации ассоциативного массива в виде бора есть следующие недостатки:
# Бор хранит строки или символы, а это значит, что у значения ключа будет ограничение на тип (строки, символы, либо числа, представленные как строки). Чтобы это исправить, научимся приводить любой тип данных к строке. Тогда сможем хранить любой вид данных в качестве ключа.
#Если реализовывать ассоциативный массив на обычном боре, а ключами будут являться строки, то будет использоваться слишком много памяти (возможен, например, вариант, когда у слов нет пересечений по префиксу, тогда бор будет использовать <tex>O(kn|S\Sigma |)</tex> памяти).
==См. также==
