Вероятностный алгоритм выбора

Question

Дано:

• Массив длины N.
• Массив содержит целые числа.
• Целые числа не обязательно отсортированы.

Найдите алгоритм, который:

• Возвращает (близкое приближение) K -й самый маленький элемент массива.
• Имеет сложность времени выполнения O (N log N) и сложность пространства O (log N).
• Алгоритм не должен быть детерминированным. В случае вероятностного алгоритма также укажите меру качества приближенного результата.

Answer 1

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

Каждый подмассив, в который возвращается быстрый выбор, может быть описан своими границами (минимальные и максимальные значения элементов, а не их индексы).Итерация по подобласти, описанной таким образом, требует O ( n ) сравнений, которые выполняются на каждом уровне рекурсии, до той же глубины, что и в быстрой сортировке: O (log n ) в среднемcase.

Быстрая сортировка также делает O ( n ) сравнений на каждом уровне рекурсии, в то время как обычный перестановочный быстрый выбор делает O ( n ) всего сравнений в среднем случаепотому что он всегда повторяется только в одном разделе).

Вот пример реализации для отдельных элементов с обычной реализацией быстрого выбора для сравнения.

Answer 2

1. Выполните итерацию по массиву один раз, чтобы найти элемент minimum и maximum.
2. Выполните итерацию по массиву, чтобы найти случайный элемент pivot между minimum и maximum (эксклюзив).
3. Выполните итерацию по массиву и подсчитайте количество элементов, меньшее или равное pivot (numSmallerEqual), и количество элементов, превышающее pivot (numBigger).
   1. Если K <= <code>numSmallerEqual, установите maximum = pivot.
   2. Иначе установите minimum = pivot.
4. If (maximum - minimum) == 0, вывод minimum, завершение.
5. If (maximum - minimum) == 1
   1. Если K <= <code>numSmallerEqual, выход minimum.
   2. Иначе выход maximum.
   3. Завершение.
6. GOTO 2:

РЕДАКТИРОВАТЬ: Исправлена ​​ошибка, указанная lVlad, до сих пор не проверен.

Answer 3

Рассматривайте проблему как нечто аналогичное быстрой сортировке. Задав элемент в массиве, вы можете получить его ранг в O (n) времени и O (lg n) пространстве. Вы можете использовать бинарный поиск, чтобы найти элемент с заданным рангом в O (lg n) итерациях этого, всего O (lg n) пространства и O (n lg n) времени.

Answer 4

Вы можете использовать подход параметризации:

Поскольку в задаче указано k, мы можем рассматривать ее как константу, поэтому пробел O (k log N) должен быть приемлемым.

1. Разделите массив на k разделов равной длины (O (1) времени и O (k log N) пространства для хранения границ раздела, потому что для каждого ключа требуется только log N space)
2. Найти наименьший элемент в каждом разделе (O (N) время и O (k log N) пространство для хранения наименьших элементов
3. возвращает максимум из k элементов, которые у вас есть (O (k) время)

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