Мне интересно, как рассчитать пространственную сложность структуры trie. Как я уже подсчитал, если глубина(длина слова) равна N, а размер шаблона K(для малых алфавитов 26) и количество слов: W Согласно моему пониманию, это должно быть: K^N
В то время как во многих местах написано, что это WxKxN.
Не могли бы вы, пожалуйста, уточнить, что правильно и как?
В худшем случае, это должно быть O(K^N)
Предположим, что длина слова равна 1, тогда будет достаточно одного массива размера k.
Пример : 'b' (позиция = 1) k = [null, указатель на другой массив размера k, null, null, null, ........]
Предположим, что длина слова равна 2, тогда нам нужно иметь массив размера k для каждого из символов, которые находятся в первой позиции в слове
Пример: "ба"
уровень 1 ('b') : [null, указатель на массив (давайте назовем его Z) на уровне 2, null, null, null, ......]
уровень 2: Z (второй символ "a") : [указатель на другой массив размера k, null, null, .......]
Допустим, мы вставляем "bc", тогда у нас будет другой массив размера k для " c "в позиции 3 (предполагая, что вы вставляете" a " в 0, затем "b" в 1 и так далее)
Поэтому на каждом уровне 0, то есть массив размером K (размер на 0 уровень: К), на уровне 2 имеем K массива размера K (размер на уровне 1: к^2), на уровне 3 мы имеем к^2 кол-во массива размера K (размер на уровне 3: к^3), и так далее.
Таким образом, сложность пространства будет равна k + k^2 + k^3 + ..... k^N (N-длина слова). Это наихудшая временная сложность.
