Обмен ближайшими соседями и относительные расстояния: различия между версиями

Обмен ближайшими соседями и относительные расстояния (посмотреть исходный код)

2 байта добавлено , 26 декабря 2015

м

4551

правка

@@ Строка 63: / Строка 63: @@
 •	Вычисление <math>D_{nni} (T_1, T_2) \;</math> представляет собой NP-полную задачу.
-•	Предположим, что <math>D_{nni}(T_1, T_2) < d \;</math>. Тогда оптимальная последовательность операций обмена ближайшими соседями, преобразующая <math>T_1 \;</math> в <math>T_2 \;</math>, может быть вычислена за время <math>O(n^2 log \; n + n \cdot 2^{23d/2})</math>.
+•	Предположим, что <math>D_{nni}(T_1, T_2) \le d \;</math>. Тогда оптимальная последовательность операций обмена ближайшими соседями, преобразующая <math>T_1 \;</math> в <math>T_2 \;</math>, может быть вычислена за время <math>O(n^2 log \; n + n \cdot 2^{23d/2})</math>.
 •	Значение <math>D_{nni}(T_1, T_2) \;</math> может быть приближенно вычислено с коэффициентом аппроксимации <math>log \; n + O(1)</math> за полиномиальное время.