Временная сложность структуры данных Trie - PullRequest
0 голосов
/ 15 мая 2018

Предполагая, что строки, которые будут сохранены в Trie, имеют длину 'n' символов. Какое будет время выполнения для insert (), search () и remove ()?

Я посмотрел в Интернете, но я не получил четкого ответа. Кто-нибудь может вкратце упомянуть, пожалуйста, сложность времени для этих трех операций.

1 Ответ

0 голосов
/ 15 мая 2018

Как указано в этой статье Википедии, и вставка, и поиск выполняются в пределах наихудшего времени выполнения, ограниченного O(n), где n - длина аргумента для вставки или поиска.Насколько я понимаю, удаление строки не является типичной особенностью структуры данных Trie.

...