4551
правка
Прямолинейное остовное дерево: различия между версиями
Материал из WEGA
Прямолинейное остовное дерево (посмотреть исходный код)
Версия от 00:25, 29 апреля 2016
, 29 апреля 2016нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 88: | Строка 88: | ||
'''Теорема 3. Пусть имеется n точек на плоскости. Алгоритм вычисления прямолинейного остовного графа строит остовный граф за время O(n log n), при этом количество ребер графа составляет O(n).''' | '''Теорема 3. Пусть имеется n точек на плоскости. Алгоритм вычисления прямолинейного остовного графа строит остовный граф за время O(n log n), при этом количество ребер графа составляет O(n).''' | ||
Доказательство. Алгоритм может рассматриваться как механизм удаления ребер из полного графа. Как было отмечено выше, все удаленные ребра являются избыточными согласно правилу циклов. Таким образом, граф на выходе алгоритма будет содержать по меньшей мере одно прямолинейное минимальное остовное дерево. | Доказательство. Алгоритм может рассматриваться как механизм удаления ребер из полного графа. Как было отмечено выше, все удаленные ребра являются избыточными согласно правилу циклов. Таким образом, граф на выходе алгоритма будет содержать по меньшей мере одно прямолинейное минимальное остовное дерево. | ||
За время работы алгоритма каждая точка будет добавлена в активное множество и удалена из него только один раз для каждой из областей <math>R_1 - R_4 \;</math>. Каждая операция вставки и удаления требует O(log n) времени. Таким образом, верхняя граница временной сложности алгоритма оказывается равной O(n log n). Хранить необходимо только активные множества, так что объем памяти для хранения не превышает O(n). □ | |||
== Применение == | == Применение == | ||
