Изменения

Перейти к: навигация, поиск

Бор

14 байт добавлено, 01:38, 14 апреля 2016
→‎Алгоритм
**Если [[Основные определения теории графов | ребра]], отмеченного очередной буквой <tex>P_i</tex> нет, то создаем новое ребро и вершину для символа строки <tex>P_i</tex>.
*Конец.
Это Построение занимает, очевидно, <tex>O(|P_1| + \ldots + |P_k|) = O(n)</tex> времени, так как поиск буквы, по которой нужно переходить, происходит за <tex>O(1)</tex>.
Поскольку на каждую вершину приходится <tex>O(1)</tex> памяти, то использование памяти есть <tex>O(n)</tex>.
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/53329»

Навигация