Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Часть 5. Алгоритмы на графах. Точные интерпретации этой нижней границы достаточно сложны, поскольку базовые операции, используемые для решения этих двух задач (сравнение координат в
Точные интерпретации этой нижней границы достаточно сложны, поскольку базовые операции, используемые для решения этих двух задач (сравнение координат в задаче сортировки и сравнение расстояний в задаче построения дерева MST), различны и ввиду того, что существует возможность использования методов, таких как поразрядная сортировка и метод перспективных сеток. Тем не менее, мы можем интерпретировать эту границу следующим образом: по мере выполнения сортировки мы должны следить за тем, чтобы алгоритм вычисления эвклидова дерева MST, который использует N lgN операций сравнения, был оптимальным, пока мы не используем числовые свойства координат; в этом случае мы можем надеяться, что он будет выполняться за линейное время (см. раздел ссылок). Интересно поразмышлять над отношениями, связывающими графы и геометрические алгоритмы, которая обусловлена решением задачи вычисления эвклидова дерева MST. Многие практические задачи, с которыми нам, возможно, придется столкнуться, могут быть сформулированы либо как геометрические задачи, либо как задачи на графах. Если преобладающим свойством является физическое расположение объектов, то можно обращаться к помощи геометрических алгоритмов, описанных в части 7; однако если фундаментальное значение приобретают взаимосвязи между объектами, алгоритмы на графах, рассмотренные в данном разделе, скорее всего, окажутся более предпочтительными. Эвклидово дерево MST, по-видимому, приходится на интерфейс между двумя этими подходами (входные данные обладают геометрическими свойствами, а элементы выходных данных взаимосвязаны), и в силу этого обстоятельства разработка простых методов вычисления эвклидова дерева MST остается труднодостижимой целью. В главе 21 мы столкнемся с подобного рода задачей, которая также приходится на этот интерфейс, но там эвклидов подход реализуется через алгоритмы, обладающие куда большим быстродействием, чем соответствующие задачи на графах.
|