Среднее время выполнения быстрого выбора

Question

Википедия утверждает, что среднее время выполнения алгоритма быстрого выбора ( Link ) равно O (n).Однако я не мог четко понять, как это так.Может ли кто-нибудь объяснить мне (через рекуррентное отношение + использование основного метода), как среднее время выполнения равно O (n)?

Answer 1

Потому что

мы уже знаем, в каком разделе находится наш желаемый элемент.

Нам не нужно сортировать (выполняя разбиение на все) все элементы, а только выполнять операции с нужным разделом.

---

Как и в быстрой сортировке, мы должны сделать разбиение пополам *, а затем пополам, но на этот раз нам нужно сделать следующий раунд только в одном одном разделе (половине ) из двух, в которых элемент должен находиться.

Это похоже (не очень точно)

n + 1/2 n + 1/4 n + 1/8 n + ..... <2 n </p>

Значит, это O (n).

_{Половина используется для удобства, фактический раздел не является точным 50%.}

Answer 2

Для анализа среднего случая быстрого выбора необходимо учитывать, насколько вероятно, что два алгоритма сравниваются во время алгоритма для каждой пары элементов и при условии случайного поворота . Из этого мы можем получить среднее количество сравнений. К сожалению, анализ, который я покажу, требует более длительных вычислений, но это чистый анализ среднего случая, в отличие от текущих ответов.

Давайте предположим, что поле, из которого мы хотим выбрать k -й самый маленький элемент, является случайной перестановкой [1,...,n]. Элементы поворота, которые мы выбираем в ходе алгоритма, также можно рассматривать как заданную случайную перестановку. Во время алгоритма мы всегда выбираем следующий возможный опорный пункт из этой перестановки, поэтому они выбираются равномерно случайным образом, так как каждый элемент имеет такую ​​же вероятность появления, что и следующий возможный элемент в случайной перестановке.

Существует одно простое, но очень важное наблюдение: мы сравниваем только два элемента i и j (с i<j) тогда и только тогда, когда один из них выбран в качестве первого элемента поворота из диапазона [min(k,i), max(k,j)]. Если сначала будет выбран другой элемент из этого диапазона, они никогда не будут сравниваться, потому что мы продолжаем поиск в подполе, где хотя бы один из элементов i,j не содержится в.

Из-за вышеприведенного наблюдения и того факта, что стержни выбираются равномерно случайным образом, вероятность сравнения между i и j составляет:

2/(max(k,j) - min(k,i) + 1)

(Два события из max(k,j) - min(k,i) + 1 возможностей.)

Мы разбили анализ на три части:

1. max(k,j) = k, следовательно i < j <= k
2. min(k,i) = k, следовательно k <= i < j
3. min(k,i) = i и max(k,j) = j, следовательно i < k < j

В третьем случае знаки менее равных опущены, потому что мы уже рассматриваем эти случаи в первых двух случаях.

Теперь давайте немного запачкаемся в вычислениях. Мы просто суммируем все вероятности, так как это дает ожидаемое количество сравнений.

Дело 1

Дело 2

Аналогично случаю 1, поэтому это остается в качестве упражнения. ;)

Дело 3

Мы используем H_r для числа r-й гармоники, которое увеличивается примерно как ln(r).

Заключение

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

Примечание: идея этого доказательства не моя. Я думаю, что это примерно стандартный анализ случаев быстрого выбора.

Если есть какие-либо ошибки, пожалуйста, сообщите мне.

Answer 3

В быстром выборе, как указано, мы применяем рекурсию только к одной половине раздела.

Анализ среднего случая:

Первый шаг: T (n) = cn + T (n / 2)

где, cn = время выполнения разбиения, где c - любая постоянная (не имеет значения).
T (n / 2) = применить рекурсию к одной половине раздела.
Поскольку это средний случай, мы предполагаем, что раздел был медианным.

Продолжая рекурсию, мы получаем следующий набор уравнений:

T (n / 2) = cn / 2 + T (n / 4)
T (n / 4) = cn / 2 + T (n / 8)
.
.
.
T (2) = c.2 + T (1)
T (1) = c.1 + ...

Суммирование уравнений и взаимное аннулирование одинаковых значений приводит к линейному результату.

c (n + n / 2 + n / 4 + ... + 2 + 1) = c (2n) // сумма GP

Следовательно, это O (n)