Алгоритмы сортировки были здесь с самого начала и были одной из наиболее изученных концепций компьютерных наук. А теперь представьте себе этот алгоритм сортировки, настолько причудливый и непредсказуемый, что он одновременно завораживает и разочаровывает тех, кто осмеливается его использовать. Правильно, мы говорим о Bogosort, алгоритме сортировки, который рандомизирует себя и многократно проверяет, отсортирован он или нет, а затем повторяет это снова и снова до бесконечности. Но в этом есть скрытая жемчужина, которая выделяет его. Итак, давайте изучим возможности этого непредсказуемого алгоритма и поймем, чем он стал другим!
Bogosort — Окончательная лотерея алгоритмов сортировки
Bogosort — это простой и понятный алгоритм сортировки, поскольку он работает путем случайного перемешивания списка элементов до тех пор, пока список не будет отсортирован.
Даже в псевдокоде сказано:
while not sorted(list):
shuffle(list)
Если список не отсортирован, алгоритм повторяет процесс до тех пор, пока он не будет отсортирован. Как вы можете себе представить, это может занять невероятно много времени, особенно для больших списков, что делает его худшим алгоритмом сортировки с точки зрения временной сложности и производительности. Это похоже на игру в лотерею, только вместо выигрыша денег вы получаете отсортированный список.
Давайте начнем понимать это в цифрах
Чтобы понять, как работает Bogosort, вот краткий пример сортировки списка из 10 элементов с помощью Bogosort. Вероятность того, что первая перетасовка будет правильной, составляет 1 из 3 628 800. У вас буквально больше шансов попасть под удар метеорита или молнии, чем отсортировать список с первой попытки с помощью Bogosort. Следующие перетасовки продолжаются с 3 628 799 и так далее, что делает его одним из самых непредсказуемых алгоритмов всех времен.
Вычислительное время
Поскольку массив строго монотонный, вероятность получения отсортированного списка равна O(n.n-1!), вплоть до 1/n! Таким образом, наилучшая временная сложность становится равной O(n), а наихудшая временная сложность буквально становится O(∞).
Перетасовывая наш путь к лабиринтам и ужинам
Несмотря на свою неэффективность, Bogosort нашел применение в некоторых реальных сценариях. Потому что иногда вместо того, чтобы искать самый быстрый путь, мы ищем самый длинный!
Простой пример — исследование лабиринта или лабиринта. Мы, конечно, можем найти самый быстрый выход, но, однако, если мы находим лабиринт красивым, мы можем наслаждаться прохождением по нему самого длинного пути, просто чтобы насладиться его красотой.
Возьмем крайне правдоподобный сценарий.
Представьте, что вы и ваши друзья пытаетесь решить, кто будет платить за ужин. И один из ваших друзей предложил, что они могут присвоить каждому человеку номера и отсортировать список с помощью Bogosort, и, в конце концов, самый низкий номер заплатит за все это! Это может занять некоторое время, но это веселый и непредсказуемый способ принятия решения. Помните, что вам может просто повезти, и вы сделаете это с первой попытки.
Это похоже на игру на удачу, где шансы сильно против вас, но если вы просто сорвете джекпот и угадаете его с первой попытки, вы выиграете большой!
Удивительные преимущества Bogosort: от принятия решений до точности сортировки
Несмотря на свою неэффективность, Богосорт имеет свои непредсказуемые преимущества. В свою защиту Bogosort может быть неэффективен для общего использования, но у него есть преимущества в определенных сценариях. Часто можно увидеть, что непредсказуемый характер сортировки Bogo приводит к творческим и инновационным решениям. Это помогает нам смотреть нестандартно, думая о неожиданных результатах, которые были бы невозможны из-за его бесконечно малого завершения.
Поскольку Bogosort не зависит от каких-либо других условий и основан на вероятностном шаблоне, он может обрабатывать широкий спектр входных данных без сбоев или неверных выходных данных, что приводит к более высокой точности сортировки, чем многие другие алгоритмы сортировки.
Можем ли мы сделать хуже?
Мы можем точно. Есть алгоритмы хуже, чем Bogosort, такие как Gorosort, Quantum Bogosort или Miracle Sort. Эти алгоритмы сделаны таким образом, чтобы иметь наихудшую производительность. Так что, строго говоря, это не алгоритмы, первое наблюдение, которое можно сделать, это то, что эти алгоритмы не гарантируют завершение работы. Поэтому, приводя к вопросу,
Можем ли мы считать «не алгоритм» «худшим алгоритмом»?
Вы также можете получить еще худший алгоритм под названием Bogobogosort. Да, вы правильно догадались, это использование Bogosort для повторной рандомизации элементов массива, для которого мы планировали использовать Bogosort. В то время как средняя сложность Bogosort была O(n!), это побило его рекорд, имея сложность O(n!1!2!3!…n!).
Чтобы дать представление о том, насколько это велико, предположим, что средний компьютер выполняет 250,000,000 операций с 32-битными целыми числами в секунду, а год равен 365 years, пузырьковая сортировка занимает 0.0000016 seconds, сортировка слиянием — 0.0000004 seconds, а сортировка Bogo — 308 years, 19 hours, 35 minutes, 22 seconds
А теперь вы можете догадаться, сколько занимает Богобогосорт?
(Ну, это выше предложенного тепла Вселенной, проверьте ответ здесь)
Заключение
Bogosort, с его бесконечным временем выполнения, безусловно, является интересной и увлекательной концепцией для изучения. Но обычно это рассматривается как шутка или новый алгоритм, а не как серьезная тема для изучения. Несмотря на то, что есть алгоритмы хуже, чем Bogosort, сложности, предлагаемые другими алгоритмами, непоследовательны и являются источником всех возможностей в теории вероятностей.
Что ж, в следующий раз, когда вам придется решать сложную задачу сортировки, не спешите отказываться от алгоритма Bogosort. Кто знает, может быть, вам повезет, и вы отсортируете свой список с первой попытки, как сорвать джекпот. По крайней мере, вы могли бы рассказать забавную историю об опыте работы с худшим алгоритмом сортировки, который оказался лучшим!
Рекомендации
- Бого-сортировка — это своего рода медленно,Макс Шерман, Вашингтонский университет, 2013 г.
- Медленная сортировка: анализ ужасно ужасных алгоритмов рандомизированной сортировки,Германн Грубер, Маркус Хольцер и Оливер Рюпп, 2007 г.
- Анализ производительности алгоритмов сортировки,Матей Хулин, 2017.
- Наихудшие алгоритмы сортировки — Чего следует избегать,
Габриэле Де Лука, 2020 г.
