4817
правок
Обмен ближайшими соседями и относительные расстояния: различия между версиями
Перейти к навигации
Перейти к поиску
Обмен ближайшими соседями и относительные расстояния (посмотреть исходный код)
Версия от 12:52, 26 декабря 2015
, 26 декабря 2015→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 70: | Строка 70: | ||
Теорема 2 ([1, 2, 3, 4]). Предположим, что деревья <math>T_1 \;</math> и <math>T_2 \;</math> взвешенные. Тогда верны следующие утверждения: | Теорема 2 ([1, 2, 3, 4]). Предположим, что деревья <math>T_1 \;</math> и <math>T_2 \;</math> взвешенные. Тогда верны следующие утверждения: | ||
• Значение | • Значение <math>D_{nni}(T_1, T_2) \;</math> может быть приближенно вычислено с коэффициентом аппроксимации <math>6 + 6 log \; n</math> за время <math>O(n^2 log \; n)</math>. | ||
• Предположим, что <math>T_1 \;</math> и <math>T_2 \;</math> могут иметь листья с неуникальными метками. Тогда вычисление | • Предположим, что <math>T_1 \;</math> и <math>T_2 \;</math> могут иметь листья с неуникальными метками. Тогда вычисление <math>D_{lcst}(T_1, T_2) \;</math> представляет собой NP-полную задачу. | ||
• Значение | • Значение <math>D_{lcst} (T_1, T_2) \;</math> может быть приближенно вычислено с коэффициентом аппроксимации 2 за время <math>O(n^2 log \; n)</math>. | ||
== Применение == | == Применение == | ||