Богосорт и O (∞)

Известный алгоритм богосорта просто перетасовывает колоду, пока она не будет в порядке

while not inOrder(deck) do
    shuffle(deck);

Сложность этого алгоритма O (∞).

Во-первых, O (∞) четко определен? Как функция может находиться в постоянном факторе бесконечности?

Во-вторых, существуют ли другие известные рандомизированные алгоритмы, которые имеют такую ​​сложную сложность? (конечно, никто никогда не будет использовать богосор...)

Наконец, для рандомизированного алгоритма мне кажется, что большую часть времени мы можем говорить только о ожидаемой сложности. Когда имеет смысл использовать big-Oh со случайными алгоритмами?

Ответы

Ответ 1

O (∞) является злоупотреблением обозначением. Если мы строго придерживаемся обозначений, это не может означать, что рост ограничен постоянным фактором бесконечности, поскольку бесконечность не является реальным числом.

Если мы примем это злоупотребление нотацией с его очевидным значением, что рост "ограничен выше на бесконечность", становится ясно, что он слишком важен для использования. В конце концов, какая функция не будет ограничена бесконечностью?

Поскольку наихудшее время работы богосорта не имеет реальной верхней границы, O (∞) - это единственное, что можно сказать об этом с большой нотной записью, которая, как мы видели, на самом деле не говорит много.

Но мы все еще можем использовать примечание "большой О", когда говорим о рандомизированных алгоритмах: нам просто нужно проанализировать все, что имеет верхние границы. Бозосор имеет наилучший вариант, и лучший случай работает в O (n) времени. И в среднем он работает в O (n * n!) Времени.