Является ли естественный разрыв Дженкса детерминированным?

Question

Т.е. будет ли алгоритм всегда возвращать один и тот же результат (для одномерного списка чисел)? Является ли естественный разрыв Фишера (O (kn log (n)) оптимизацией Дженкса) детерминированным?

Answer 1

Естественный разрыв Фишера использует динамическое программирование для нахождения оптимального решения и является детерминированным.

Есть два варианта естественных разрывов Дженка.

1. Один метод перемещает одну единицу из класса с наибольшей дисперсией в класс с наименьшим. Этот метод не всегда возвращает оптимальный ответ. Это основано на произвольных начальных классах, поэтому не является детерминированным.
2. Альтернативный метод проверяет все разделы, он всегда возвращает оптимальный ответ и является детерминированным.

На этой странице представлено доказательство оптимальности алгоритма Фишера и отмечается, что основной алгоритм Дженка не дает оптимального ответа:

Итеративное перемещение значений из классов с высокой вариацией в классы с низкой вариацией обсуждается в Википедии, которая не всегда приводит к оптимальному решению.