Среднее время выполнения Quickselect

Ответ 1

Поскольку

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

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

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

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

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

Итак, это O (n).

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

Ответ 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 возможностей.)

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

• max(k,j) = k, поэтому i < j <= k
• min(k,i) = k, поэтому k <= i < j
• min(k,i) = i и max(k,j) = j, поэтому i < k < j

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

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

Случай 1

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

Случай 2

Подобно случаю 1, поэтому это остается как упражнение.;)

Случай 3

Заключение

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

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

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

Ответ 3

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

Средний анализ:

Первый шаг: 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)