Может кто-нибудь, пожалуйста, дать полное объяснение того, что будет средним временем выполнения богосорта?Bogo-sort среднее время исполнения
Psuedocode для алгоритма:
while not isInOrder(deck):
shuffle(deck)
Может кто-нибудь, пожалуйста, дать полное объяснение того, что будет средним временем выполнения богосорта?Bogo-sort среднее время исполнения
Psuedocode для алгоритма:
while not isInOrder(deck):
shuffle(deck)
Есть n!
перестановок, только один из которых является правильным (в предположении отдельных элементов). Поэтому в ручном смысле вы ожидаете выбрать правильный ответ после примерно O(n!)
итераций. * Но каждая операция тасования/проверки сама по себе O(n)
. Следовательно, O(n.n!)
в целом.
Среднее число попыток выполнить операцию обратное к вероятности каждой попытки.
Есть n!
способы перетасовки n
элементы. Если все элементы различны, только один способ создает сортированный вывод. Таким образом, вероятность сортировки shuffle равна 1/n!
, а среднее число попыток - n!
.
Каждый случайный выбор занимает O(n)
времени (при условии, что Fisher-Yates перемещается или что-либо в равной степени разумно).
Таким образом, временная сложность O(n!*n)
.
'O ((n + 1)!) = O (n! * N)' – SomeWittyUsername
@icepack не уверен в равенстве, но 'O ((n + 1)!)' Является надмножеством 'O (n! * п) '. Я не думал, что это стоит включить в ответ. –
@JanDvorak: Да, они эквивалентны (n + 1)! = (n + 1) n! = (n! + n.n!). –
Предполагая равномерное распределение, в среднем будут выполняться попытки «n!/2», а не 'n!', А не то, что он меняет сложность. – SomeWittyUsername
@icepack: Ах, хороший звонок! –
@icepack why 'n!/2'? –