Алгоритм выбора наименьшего числа

Question

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

Проблема: Учитывая неупорядоченный массив целых чисел, найдите мой самый маленький элемент в массиве

а.Алгоритм Randomized_Select прост.Но я не могу понять математику, которая объясняет, что это рабочее время.Можно ли объяснить это, не делая глубокие математические, более интуитивным способом?Что касается меня, я думаю, что это должно работать для O (nlog n), а в худшем случае это должно быть O (n ^ 2), как быстрая сортировка.В avg randomizedPartition возвращает ближнюю середину массива, а массив делится на два каждого вызова, а следующий вызов рекурсии обрабатывает только половину массива.RandomizedPartition стоит (p-r + 1) <= n, поэтому мы имеем O (n * log n).В худшем случае он будет каждый раз выбирать максимальный элемент в массиве и делить массив на две части - (n-1) и (0) каждый шаг.Это O (n ^ 2) </p>

Следующий (алгоритм выбора) более непонятен, чем предыдущий:

b.Какая разница по сравнению с предыдущим.Это быстрее в среднем?

с.Алгоритм состоит из пяти шагов.В первой части мы разбиваем массив на n / 5 частей, каждая из которых состоит из 5 элементов (кроме последней).Затем каждая часть сортируется с использованием сортировки вставкой, и мы выбираем 3-й элемент (медиана) каждой.Поскольку мы отсортировали эти элементы, мы можем быть уверены, что предыдущие два <= этого элемента сводки, а последние два>> = тогда.Затем нам нужно выбрать элемент avg среди медиан.В книге указано, что мы рекурсивно называем алгоритм выбора для этих медиан.Как мы можем это сделать?В алгоритме выбора мы используем сортировку вставками, и если мы меняем две медианы, нам нужно поменять местами все четыре (или даже больше, если это более глубокий шаг) элементы, которые являются «дочерними» для каждой медианы.Или мы создаем новый массив, который содержит только ранее выбранные медианы, и ищем ли среди них медианы?Если да, то как мы можем заполнить их в исходном массиве, как мы ранее изменили их порядок.

Другие шаги довольно просты и выглядят как в алгоритме randomized_partition.

Answer 1

Рандомизированный прогон выбора в O (n).посмотрите на этот анализ .

Algorithm :
Randomly choose an element
split the set in "lower than" set L and "bigger than" set B
if the size of "lower than" is j-1 we found it
if the size is bigger, then Lookup in L
or lookup in B

Общая стоимость равна сумме:

• Стоимость разбиения массива размером n
• Стоимость поиска в L или стоимость поиска в B

Отредактировано: я пытался реструктурировать свой пост

Вы можете заметить, что:

• Мы всегда идем дальше в наборе с большим количеством элементов
• Количество элементов в этом наборе составляет n - rank(xj)
• 1 <= rank(xi) <= n Итак 1 <= n - rank(xj) <= n
• Случайность элемента xj напрямую влияет на случайность числа элементов, которые больше xj (и которые меньше xj)

, еслиxj - выбранный элемент, тогда вы знаете, что стоимость составляет O(n) + cost(n - rank(xj)).Давайте назовем rank(xj) = rj.

. Чтобы дать хорошую оценку, нам нужно принять ожидаемое значение общей стоимости, которое является

T(n) = E(cost) = sum {each possible xj}p(xj)(O(n) + T(n - rank(xj)))

xj случайным.После этого это чистая математика.Мы получаем:

T(n) = 1/n *( O(n) + sum {all possible values of rj when we continue}(O(n) + T(n - rj))) )
T(n) = 1/n *( O(n) + sum {1 < rj < n, rj != i}(O(n) + T(n - rj))) )

Здесь вы можете изменить переменную, vj = n - rj

T(n) = 1/n *( O(n) + sum { 0 <= vj <= n - 1, vj!= n-i}(O(n) + T(vj) ))

Мы ставим O (n) вне суммы, получим коэффициент

T(n) = 1/n *( O(n) + O(n^2) + sum {1 <= vj <= n -1, vj!= n-i}( T(vj) ))

Мы помещаем O (n) и O (n ^ 2) снаружи, теряем коэффициент

T(n) = O(1) + O(n) + 1/n *( sum { 0 <= vj <= n -1, vj!= n-i} T(vj) )

Проверьте ссылку на то, как это вычисляется.

Длянерандомизированная версия:

Вы говорите сами: В avto randomizedPartition возвращает середину массива .

Именно поэтому работает рандомизированный алгоритм, и именно он используется для построения детерминированного алгоритма.В идеале вы хотите выбрать опорную точку детерминистически, чтобы она давала хорошее разделение, но наилучшее значение для хорошего разделения - это уже решение!Таким образом, на каждом шаге они хотят получить достаточно хорошее значение: "по крайней мере 3/10 массива ниже оси и по крайней мере 3/10 массива выше" .Чтобы добиться этого, они делят исходный массив на 5 на каждом шаге, и снова это математический выбор.

Answer 2

Я однажды создал объяснение этому (со схемой) на странице Википедии для него ... http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm