Нахождение k-ых квантилей из набора n-элементов.(Из кормена)

Question

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

Прямым решением было бы выбрать каждый k, 2k, 3k ... ik наименьший элемент, время работы которого равно O (kn) (k вызывает выбор процедуры O (n)).Но это можно оптимизировать, чтобы добиться большего успеха, чем O (kn).После нахождения медианы медиан по индексу 'i' в процедуре выбора мы делаем следующий рекурсивный вызов.

, если индекс медианы медиан i>> k, рекурсивно вызываем select kth наименьший элементв левом подмассиве A [0 ... i]

, если i

Можно ли изменить приведенные выше рекурсивные вызовы, как показано ниже, что уменьшило бы коэффициент 'k' до 'log k'?

, если индекс медианы i равен> k, рекурсивновыберите k-й наименьший элемент в левом подмассиве A [0 ... i], а также рекурсивно выберите n - k-й наименьший элемент в правом подмассиве A [i + 1 ... n].

, еслиi

Основной вызов будет просто выбрать (A, k, n).

Answer 1

Обратите внимание, что мы используем модифицированный PARTITION, которому присваивается индекс для оси, который будет использоваться в качестве последнего входного параметра.

Вы начинаете с KTH-QUANTILES(A, 1, n, 1, k-1, k)

KTH-QUANTILES(A, p, r, i, j, k)
n=A.length
m=floor((i+j)/2)
q=floor(m(n/k))
q=q-p+1
q=SELECT(A, p, r, q)
q=PARTITION(A, p, r, q)
if i<m
    L=KTH-QUANTILES(A, p, q-1, i, m-1, k)
if m<j
    R=KTH-QUANTILES(A, q+1, r, m+1, j, k)
return L U A[q] U R

Глубина дерева рекурсии составляет lg k, поскольку разбиение выполняется вокруг медианы заданной статистики порядка (от i до j).

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

Answer 2

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

Я предполагаю, что у нас есть O (n) алгоритм поиска статистики. Таким образом, я могу найти k-ую статистику за O (n) время. Предположим, я говорю, что найду все n / k k-ые квантили, используя функцию «разделяй и властвуй», так что:

Если у меня n 'элементов, я разбиваю массив на n' / 2 части, сообщаю границу k-го квантиля для обоих n '/ 2 разделов. И сообщать об оставшихся квантилях рекурсивно. По сути, я делаю, что после разбиения с использованием медианы я извлекаю самый правый квантиль из левого массива, самый левый квантиль из правого разбиения и после обрезки этих массивов запускаю алгоритм рекурсивно. Мой анализ сложности выглядит так:

T (n, k) = 2 * T (n / 2, k / 2) + O (n).

Это оказывается O (nlogk), так как часть k / 2 будет сходиться быстрее, хотя вы можете решить это более строго. Также мы использовали это n> k (очевидно из проблемы. Обратите внимание, что задача выделения 2 квантилей и обрезки массива будет выполнена в O (n)