БК-дерево сложность
Для школы нам нужно было создать BK-дерево с функциями insert() и get(). Функция get() допускает, что max_distance будет только 1, поэтому к результатам будут добавлены только результаты в пределах расстояния 1 (LD-distance).
Теперь нам нужно рассчитать время и сложность памяти для RB-дерева, с чем я немного борюсь.
Если я правильно понимаю, для вставки вы начинаете с корня, рассчитываете расстояние с корнем, и если ребенок с таким расстоянием ("весом") уже существует, вы начинаете снова, но с этого поддерева. В противном случае вы добавляете узел с весом = расстояние. Я бы сказал, что для этого нужно учитывать среднюю длину слова в словаре, давайте назовем это L. Теперь каждый узел будет иметь (поправьте меня, если я ошибаюсь) в среднем L детей, что означает, что высота дерева будет зависеть от количества слов (предположим, все из словаря). Я бы сказал, высота = LogL(количество слов) (так что L^ высота = количество слов), во-первых, это правильно?
Тогда это также будет сложность по времени для функции insert(), если я не ошибаюсь?
Теперь функция get() немного сложнее, поскольку вы можете / будете иметь (наиболее вероятно) несколько результатов. Мы должны были использовать max_distance = 1, как я сказал. Сначала вы смотрите на расстояние с корнем, и идете дальше со всеми потомками, которые находятся в [расстояние с корнем - 1, расстояние с корнем +1], и делаете это снова, и каждый раз, когда вы ударяете узел с расстоянием <=1 с помощью учитывая get-word, вам нужно будет добавить это в ваш массив результатов. Теперь у вас может быть максимум 3 ребенка, где вы продолжаете для каждого узла. Так что здесь моя логика заключается в том, что вы всегда идете по 3 из L узлов (в максимуме, в худшем случае), снова и снова. это означает, что вы пропустите (L-3)^ высоту узлов, что также будет сложностью по времени, это кажется немного странным.
Извините за плохую грамматику, английский не мой родной язык.
Заранее спасибо!
Ps: я использовал динамическую версию программирования в Python, чтобы сделать функцию LD-расстояния. Не знаю, нужно ли вам вычислять это и в ваших вычислениях, я так не думаю, поскольку вы добавляете расстояние как вес при вставке, так что вам нужно будет сделать это только один раз во вставке, но никогда в получении,