Изменения

Перейти к: навигация, поиск

Convex hull trick

5 байт добавлено, 01:09, 18 января 2017
Нет описания правки
Convex hull переводится с английского как выпуклая оболочка[http://neerc.ifmo.ru/wiki/index.php?title=Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull]. Convex hull trick - один из методов оптимизации динамического программирования[http://neerc.ifmo.ru/wiki/index.php?title=Динамическое_программирование], использующий идею выпуклой оболочки. Позволяет улучшить ассимптотику решения некоторых задач, решемых методом динамического программирования с <math>O(n^2)</math> до <mathtex>O(n*logn\cdot\log(n))</mathtex>. Техника впервые появилась в 1995 году (задачу на нее предложили в USACO - национальной олимпиаде США по программированию). Массовую известность получила после IOI (международной олимпиады по программированию для школьников) 2002
==Пример задачи, решаемой методом convex hull trick==
Анонимный участник

Навигация