Я разработал программу для реализации алгоритма подарочной упаковки для нахождения выпуклого корпуса. Есть ли способ генерировать набор точек, который служит наихудшим вариантом для этого алгоритма?Что является наихудшим вариантом для алгоритма подарочного wapping (алгоритм Джарвиса) для вычисления выпуклого корпуса?
Как я могу создать такой случай?
Предположим, у вас есть множество точек - S. Когда на каждой итерации вы вычитать одну точку из S и добавить эту точку на выпуклой оболочки, и вы должны проверить каждую точку, что еще осталось в S.
The время выполнения зависит от размера вывода, поэтому марш Джарвиса является чувствительным к выходу алгоритмом.
Таким образом, большая мощность - больше времени. И это может быть достигнуто на множестве, являющемся выпуклой оболочкой.
Вероятно, самый простой способ создания такой выпуклой оболочки n указывает на то, чтобы все точки на круге были установлены.
Если я прав, в худшем случае, когда Н = Н, то есть тестовый набор образован вершинами выпуклого многоугольника. –