0
Итак, у меня есть список имен, которые я использую для создания графика. Каждое имя является узлом на графике, а края взвешиваются с минимальным расстоянием редактирования между именами. Для моей задачи я должен создать взвешенную границу между каждым именем. У меня есть вложенный цикл для этого, и для моей программы требуется много времени для построения графика. Есть ли более быстрый способ сделать это?Более быстрый способ создания полного графика?
Вам действительно нужны все края? Возможно, вы могли бы создать их лениво, т. Е. Только вычислить вес, когда это необходимо в первый раз. – Henrik
Ну, после того, как у меня есть полный график, я предполагаю запустить алгоритм MST Prim на нем из любого произвольного узла ... –
Как упоминается ниже @ user2079303, создание ребер должно быть O (n^2) - нет способа избежать что. Однако, возможно, ваша функция «минимального расстояния редактирования» плохо работает ...? В зависимости от того, какой алгоритм вы используете, это может быть экспоненциальным (наивный рекурсивный алгоритм) или O (mn) для длин двух строк, которые могут быстро складываться, если ваши имена длинны ... – twalberg