Время выполнения случайной сортировки

Question

Как бы вы описали время выполнения такого рода, учитывая функцию sorted, которая возвращает True, если список отсортирован и выполняется в O (n):

def sort(l):
    while not sorted(l): random.shuffle(l)

Предположим, что тасование совершенно случайно.

Будет ли это написано в нотации big-O? Или есть какой-то другой способ классификации алгоритмов со случайными компонентами?

Answer 1

Этот алгоритм называется Bogosort . Это экземпляр класса алгоритмов под названием Алгоритмы Лас-Вегаса . Лас-Вегасские алгоритмы - это рандомизированные алгоритмы , которые всегда гарантируют правильные результаты, но не дают никаких гарантий относительно вычислительных ресурсов.

Временная сложность Богосорта не может быть прямо выражена в Обозначение Бахманна-Ландау из-за его вероятностного характера. Однако мы можем сделать заявление о его ожидаемой сложности со временем. Ожидаемая сложность времени Bogosort составляет O(n·n!).

Answer 2

Хотите верьте, хотите нет, но для этого есть вики: http://en.wikipedia.org/wiki/Bogosort

Средний регистр: O (N * N!)

Answer 3

Средний случай действительно 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)

2) Для рандомизированных алгоритмов бессмысленно проводить анализ «наихудшего случая». Вы можете придумать казнь, которая будет очень плохой.

3) Действительно плохие казни происходят с набором меры 0 (вероятностный специалист сказал бы, что они «почти наверняка» не происходят). Их на самом деле невозможно наблюдать.

Answer 4

Система обозначений Big-O предполагает худший вариант развития событий. В худшем случае этот алгоритм никогда не завершается.