Провожу исследовательскую работу на тему сортировок массивов. В процессе возник один вопрос. Можно ли узнать, сколько перестановок совершит программа для наихудшего случая, зная сложность алгоритма?
-
1Знаю, что есть один алгоритм, который рандомно переставляет элементы, затем проверяет - отсортирован ли массив(вроде болотный называется). Так вот в нем наихудший случай - бесконечность.– Silento9 апр 2017 в 13:23
-
1@Silento это Bogosort или Shotgun Sort– Mikhail Vaysman9 апр 2017 в 13:25
-
Смотрите в Википедии Список алгоритмов сортировки, там указана сложность.– Alexander Petrov9 апр 2017 в 14:01
1 ответ
Есть разные меры сложности. Для ответа важны две: сложность в среднем, и сложность в наихудшем случае.
Последний вариант неинтересен: если известна сложность алгоритма в наихудшем случае, то есть число операций в наихудшем случае, то вопрос вырождается в тавтологию.
Первый вариант интереснее - если известна сложность алгоритма в среднем, можем ли мы сказать что-нибудь о сложности в наихудшем случае. Если и можем, то немногое. Алгоритмы сортировки слиянием и быстрой сортировки имеют одинаковую асимптотику сложности в среднем, O(n log n), однако, в наихудшем случае сортировка слиянием также имеет асимптотику O(n log n), в то время как быстрая сортировка в наихудшем случае имеет сложность O(n^2). Этот пример показывает, что сложность в среднем не позволяет делать однозначных выводов о сложности в наихудшем случае.