Поиск лучшего случая, худшего случая и среднего случая для неизвестного алгоритма

Мне дали абзац, объясняющий, что делает неизвестный алгоритм:

Алгоритм проверяет, отсортирован ли список целых чисел, он начинает с начала списка и сканирует до тех пор, пока следующая пара элементов не окажется не в порядке. В этом случае алгоритм возвращает false. В других случаях (т. е. список целых чисел отсортирован) алгоритм вернет true.

Я выяснил, что время выполнения этого алгоритма в худшем случае для входного списка из n элементов O (n). В лучшем случае время работы этого алгоритма на входном списке с n элементами равно Ω(2). Каким будет среднее ожидаемое время выполнения для входного списка со случайной перестановкой чисел от 1,2 до n? Я действительно не уверен, правильные ли мои ответы или нет...

Я не думаю, что лучший случай Ом ( 2 ) .; он все равно должен просмотреть весь список.
Среднее время работы зависит от распределения входных данных. Во всяком случае, в большой нотации O вы можете сказать, что это О ( н ) потому что оно не может превышать время работы в наихудшем случае. Но если вы хотите большой Θ , вам нужно знать входное распределение.
@EricTressler Я предполагаю, что OP означает, что первые три элемента в последовательности не отсортированы.
Истинный; моя вина.

Ответы (1)

Если список распределен равномерно, его к первые элементы упорядочиваются по возрастанию с вероятностью 1 / к ! и они упорядочены по убыванию вероятности 1 / к ! отсюда и номер Н количество сравнений, необходимых алгоритму, таково, что п [ Н ⩾ к ] "=" 2 / к ! для каждого 2 ⩽ к ⩽ н − 1 . Таким образом, для каждого н ⩾ 3 , это видно 2 ⩽ Е [ Н ] ⩽ 2 е − 3 , в частности Е [ Н ] "=" Θ ( 1 ) .

Я предполагаю, что «отсортировано» означает «увеличение».
Поиск лучшего случая, худшего случая и среднего случая для неизвестного алгоритма
СпросиСетьПолитика конфиденциальности1y, 0v