Время выполнения случайной сортировки
Как бы вы описали время выполнения этого вида, учитывая функцию sorted, которая возвращает True, если список отсортирован и выполняется за O (n):
def sort(l):
while not sorted(l): random.shuffle(l)
Предположим, что перемешивание совершенно случайное.
Было бы это записано в нотации с большим О? Или есть другой способ категоризации алгоритмов со случайными компонентами?
Ответы 4
Вы не поверите, но для этого есть вики-запись: http://en.wikipedia.org/wiki/Bogosort
Средний случай: O (N * N!)
Однако худший случай маловероятен. Но средний случай все равно отстой :-)
Обозначение Big-O предполагает наихудший сценарий. В худшем случае этот алгоритм никогда не завершается.
В конечном итоге он прекратится, поскольку случайное перемешивание действительно случайное (согласно описанию проблемы), оно в конечном итоге приведет к правильному перемешиванию.
Нет, SoapBox, для гарантированного завершения этого алгоритма необходимо гарантировать, что случайная функция произведет определенный порядок (отсортированный). Но если у него есть гарантия создания такого заказа, то это не совсем случайность.
Если перемешивание действительно случайное, всегда есть случай хуже, чем данный случай. Есть случай, на который потребуется миллиард циклов; есть случай, который займет 10 ^ 10 ^ 10 ^ 10 ^ 10 циклов. «Худший» случай хуже их обоих! Ergo это никогда не кончится.
Вероятность завершения этого никогда равна нулю. Таким образом, вы можете сказать, что вам почти гарантировано, что он закончится :-).
О, это гарантированно закончится - если вам не надоест через несколько недель, и вы просто нажмете Ctrl-C.
Нотация Big-O не предполагает наихудшего сценария. Обозначение Big-O часто используется для описания сложности наихудшего случая, но может использоваться и для других случаев.
Нотация Big-O предполагает наихудший сценарий. Другие буквы (Тета, Омега) используются для других случаев. en.wikipedia.org/wiki/Big_O_notation
Нет. Нотация Big-O описывает верхнюю границу и может использоваться при анализе различных случаев. Тета, Омега и т. д. Описывают другие границы и также могут применяться к анализу наихудшего случая.
Этот алгоритм называется Богосорт. Это экземпляр класса алгоритмов под названием Алгоритмы Лас-Вегаса. Алгоритмы Лас-Вегаса - Рандомизированные алгоритмы, которые всегда гарантируют правильные результаты, но не дают никаких гарантий относительно вычислительных ресурсов.
Временная сложность Bogosort не может быть напрямую выражена в Обозначения Бахмана-Ландау из-за его вероятностной природы. Однако мы может делаем заявление о его временной сложности ожидал. Ожидаемая временная сложность Bogosort - O(n·n!).
Так это полиномиально? Как это, по крайней мере, не экспоненциально?
Shinzou n*n! намного больше n^2. Он больше экспоненты. Итак, где n^2 означает n\*n; уравнение здесь n * n! означает n * (n * (n-1) * (n-2) * (n-3) * (n-4) * ... * (n-(n-1)))
В среднем это действительно O (N N!):
Обратите внимание, что их ровно N! перестановки N элементов. Вероятность выбрать правильный составляет ровно 1 / N !. Следовательно, по строгому закону больших чисел ожидаемое количество перемешиваний равно N !.
Откуда появился другой фактор N? Вы должны на каждом этапе проверять, какую перестановку вы выбрали. Это можно сделать линейно, сравнивая соседние элементы. Отсюда дополнительный множитель N.
Комментарии выше показали, что запись O (g (n)) является «наихудшим случаем»:
1) Это неправда. Определение O (g (n)): f (n) равно O (g (n)), если существуют некоторые c, d такие, что f (n) <c * g (n) + d для достаточно большого n. Нет ничего о «худшем случае». Так уж получилось, что g (n) является большей функцией, чем f (n), но чисто математическое определение ничего не говорит о «case».
2) Для рандомизированных алгоритмов в любом случае бессмысленно проводить анализ «наихудшего случая». Вы можете придумать какое-нибудь исполнение, которое будет действительно плохим.
3) Действительно плохие исполнения происходят на множестве меры 0 (вероятностный специалист сказал бы, что они «почти наверняка» не происходят). Их фактически невозможно наблюдать.
«Их на самом деле невозможно наблюдать». - например, совершенно в стороне от философских дискуссий о том, гарантированно ли случайный генератор в конечном итоге произведет все выходные данные в своем диапазоне, потому что вы умрете первым ;-)
Но алгоритм не проверяет предыдущие перестановки, поэтому они могут повторяться бесконечно.
Большая O - наиболее часто используемая асимптотическая запись, так что это означает, что n приближается к бесконечности. Допустим, что по мере того, как n приближается к бесконечности, все еще существует вероятность того, что самая первая перетасовка сортирует колоду ... Но на самом деле, чем больше n, тем меньше вероятность, что она вернется через n * n! время. Я бы сказал, что это O (бесконечность). Тем не менее, алгоритмы Лас-Вегаса не имеют стандартной нотации Бахмана-Ландау.
Но в худшем случае вероятность равна 0, что в среднем хорошо :-)