304
правки
Изменения
Нет описания правки
|}
Линия, полученная в результате работы алгоритма, отражается пунктирной линией.
===Время работы===
Ожидаемая сложность алгоритма может быть оценена выражением <tex>T(n) = 2T\left(\frac{n}{2}\right) + O(n)</tex>, которая упрощается в <tex>T(n) \in \Theta(n\log n)</tex>. Однако в худшем случае сложность алгоритма <tex>O\left(n^2\right)</tex>.
===Замечания к алгоритму===
====Топология====
К сожалению, алгоритм Дугласа-Пекера в ходе своей работы топологию не сохраняет, что означает в ответе мы можем получить линию с самопересечениями.
====Оптимальность====
[[Файл:DP(1).png|100px|thumb|right|Оптимальный по количеству точек ответ]]
[[Файл:DP(2).png|100px|thumb|left|Ответ алгоритма Дугласа-Пекера]]
Алгоритм может находить не минимальный по количеству точек ответ. Рассмотрим пример, где исходная линия с некоторым приближением будет представлять полуокружность. Мы можем подобрать такое епсилон, что алгоритм добавит три точки помимо стартовой и конечной(точки через каждую четверть исходного пути), в то же время мы можем взять две точки через
каждую треть исходного пути, для которых упрощение так же верно.
