Shtirlitz писал(а):Source of the post
А не могли бы вы немного пояснить на этом примере, как мы здесь считаем трудоёмкость? Почему логарифм берём?...
Так как дитохомический алгоритм основан на делении пополам, поэтому для оценки трудоемкости берется логарифм по основанию 2 от общего числа вариантов.
Shtirlitz писал(а):Source of the post
Но если я правильно понимаю, то алгоритм этот с максимальным расстоянием всё-таки не является верным для данной задачи?...
Equinoxe писал(а):Source of the post А вот и весь алгоритм:
Алгоритм рекурсивный, за аргументы он берет два множества точек S и Q. Он считает минимальную окружность для S и Q, считая, что каждая точка Q лежит на границе возможной минимальной окружности. Так, сама задача решается вызовом алгоритма с S=исходным точкам, а Q — пустому множеству. Т.к. алгоритм вызывает себя рекурсивно, он будет увеличивать Q пока он не будет содержать все граничные точки окружноти.
Алгоритм обрабатывает точки S в случайном порядке, поддерживая множество P обработанных точек и минимальную окружность, охватывающую P и Q. На каждом шаге алгоритм проверяет, входит ли очередная точка r в окружность, если нет, то алгоритм заменяет текущую окружность на результат алгоритма со множествами P и Q+r. Независимо от того, изменилась окружность или нет, r включается во множество P. Обработка каждой точки, таким образом, состоит из проверки за константное время, лежит ли точка в окружности, и возможно ещё один рекурсивный вызов алгоритма. Можно показать, что i-тая точка имеет вероятность рекурсивного вызова O(1/i), и таким образом время линейно
(Правда мне нерекурсивный вариант рассказывали)
Shtirlitz писал(а):Source of the post
[url=http://prografix.narod.ru/min_circle.html]http://prografix.narod.ru/min_circle.html[/url]
Не могли бы вы подсказать, как посчитать трудоёмкость данного алгоритма?
Вернуться в «Школьная математика»
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 2 гостей
