Алгоритм - Как отсортировать массив 0/1 с 2n / 3 сравнений?

Question

В Руководство по разработке алгоритма , такой акциз есть

4-26 Рассмотрим проблему сортировки последовательности n и 1 с использованием сравнения. Для каждого сравнения двух значений x и y алгоритм узнает, что из x y выполняется.

(a) Дайте алгоритм сортировки в n - 1 сравнениях в худшем случае. Покажите, что ваш алгоритм оптимален.

(b) Дайте алгоритм сортировки в 2n / 3 сравнений в среднем случае (при условии, что каждый из n входов равен 0 или 1 с равной вероятностью). Шоу что ваш алгоритм оптимален.

Для (а) я думаю, что это довольно легко. Я могу выбрать [n-1] в качестве точки поворота, затем сделать что-то похожее на раздел быстрой сортировки, отсканировать от 0 до n - 2, найти среднюю точку, где левая сторона - все 0, а правая - все 1, для этого потребуется n - 1 сравнений. .

Но из-за (б) я не могу понять. "каждый из n входов равен 0 или 1 с равной вероятностью" , так что я могу предположить, что числа 0 и 1 равны? Но как я могу получить результат, который связан с 1/3? разделить весь массив на 3 группы?

Спасибо

Answer 1

«0 или 1 с равной вероятностью» - это условие для «среднего» случая. В других случаях сроки могут быть хуже.

Подсказка 1: 2/3 = 1/2 + 1/8 + 1/32 + 1/128 + ...

Подсказка 2: Рассмотрите последовательность как последовательность пар и сравните элементы в каждой паре. Половина вернется равным; половина не будет. Из половины неравных вы знаете, какой элемент в паре равен 0, а какой - 1, поэтому не нужно больше сравнивать.

Answer 2

Нет, это означает, что в любой позиции у вас есть одинаковый шанс (вероятность) того, что входное значение равно 0 или 1. Это даст вам первую подсказку: ваш алгоритм будет рандомизирован.

Время выполнения будет зависеть от некоторой случайной величины, и вам нужно принять ожидаемое значение, чтобы получить случай средней сложности .Обратите внимание, что в этом случае вам необходимо детализировать во время анализа сложности, поскольку они требуют точной константы (2/3n, а не просто O(n))

Редактировать:
Подсказка .В отсортированном массиве (тот, который вы получаете в конце), единственное, что меняется, зная, что у вас есть только 2 возможных элемента.