Bogo-sort среднее время исполнения

Question

Может кто-нибудь, пожалуйста, дать полное объяснение того, что будет средним временем выполнения богосорта?

Psuedocode для алгоритма:

while not isInOrder(deck): 
    shuffle(deck) 

Answer 1

Есть n! перестановок, только один из которых является правильным (в предположении отдельных элементов). Поэтому в ручном смысле вы ожидаете выбрать правильный ответ после примерно O(n!) итераций. ^* Но каждая операция тасования/проверки сама по себе O(n). Следовательно, O(n.n!) в целом.

---

_{* Для того, чтобы быть точным, вы можете моделировать как geometrically-distributed random variable с параметром р = 1/п!. Ожидаемое значение такой переменной: 1/p = n!.}

Answer 2

Среднее число попыток выполнить операцию обратное к вероятности каждой попытки.

Есть n! способы перетасовки n элементы. Если все элементы различны, только один способ создает сортированный вывод. Таким образом, вероятность сортировки shuffle равна 1/n!, а среднее число попыток - n!.

Каждый случайный выбор занимает O(n) времени (при условии, что Fisher-Yates перемещается или что-либо в равной степени разумно).

Таким образом, временная сложность O(n!*n).