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

Question

Хорошо известный алгоритм bogosort просто перетасовывает колоду до тех пор, пока не упорядочится

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

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

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

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

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

Answer 1

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

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

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

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