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