Что именно представляет собой наихудший ввод различных алгоритмов сортировки?

Это связано с этим вопросом.

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

Например, согласно этому сообщению, наихудший случай сортировки слиянием выглядит совсем иначе, чем просто массив с числами в порядке убывания .

Итак, мой вопрос заключается в том , что именно представляет собой наихудший сценарий алгоритма. Можно ли это официально представить? И есть ли способ/метод получения/доказательства этого из алгоритма?

Ответы (1)

Формальное определение сценария наихудшего случая состоит в том, что это вход, для которого при заданном размере алгоритм выполняет максимальное количество шагов. Таких входов может быть несколько.

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

Я бы добавил к вашему определению «для заданного размера ввода».
@RobertIsrael Готово, спасибо. Вы могли бы.
Для данного н , вы можете выполнить перебор возможных входных данных размера н чтобы найти тот, который делает больше всего шагов. Но нет никакой гарантии, что вы сможете обобщить это на всех. н .
@EthanBolker Да, но есть ли формальный способ их вычислить?
@ ng.newbie Не в зависимости от алгоритма. Для каждого алгоритма (или, возможно, класса алгоритмов) вы можете найти/вывести способ вычисления входных данных для наихудшего случая.
Что именно представляет собой наихудший ввод различных алгоритмов сортировки?
СпросиСетьПолитика конфиденциальности1y, 0v