4551
правка
Прямолинейное остовное дерево: различия между версиями
Материал из WEGA
Прямолинейное остовное дерево (посмотреть исходный код)
Версия от 00:24, 29 апреля 2016
, 29 апреля 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 70: | Строка 70: | ||
'''for''' (i = 0; i < 2; i + +) { | '''for''' (i = 0; i < 2; i + +) { | ||
'''if''' (i == 0) отсортировать точки согласно x + y; | '''if''' (i == 0) отсортировать точки согласно порядку x + y; | ||
'''else''' отсортировать точки согласно x - y; | '''else''' отсортировать точки согласно порядку x - y; | ||
A[l] = A[2] = <math>\empty</math> | A[l] = A[2] = <math>\empty</math> | ||
'''for''' каждой точки | '''for''' каждой точки p по порядку { | ||
найти точки в А[1], А[2], такие, что p находится в их областях <math>R_{2i+1}</math> и <math>R_{2i+2}</math>, соответственно; | найти точки в А[1], А[2], такие, что p находится в их областях <math>R_{2i+1}</math> и <math>R_{2i+2}</math>, соответственно; | ||
соединить p с ближайшей точкой каждого подмножества; | соединить p с ближайшей точкой каждого подмножества; | ||
| Строка 93: | Строка 93: | ||
За время работы алгоритма каждая точка будет добавлена в активное множество и удалена из него только один раз для каждой из областей <math>R_1 - R_4 \;</math>. Каждая операция вставки и удаления требует O(log n) времени. Таким образом, верхняя граница временной сложности алгоритма O(n log n). Хранить необходимо только активные множества, так что объем памяти для хранения не превышает O(n). □ | За время работы алгоритма каждая точка будет добавлена в активное множество и удалена из него только один раз для каждой из областей <math>R_1 - R_4 \;</math>. Каждая операция вставки и удаления требует O(log n) времени. Таким образом, верхняя граница временной сложности алгоритма оказывается равной O(n log n). Хранить необходимо только активные множества, так что объем памяти для хранения не превышает O(n). □ | ||
== Применение == | == Применение == | ||
