Медиана медиан

Медиана медиан
	Медиана медиан
Сорт	Алгоритм выбора
Структура данных	Множество
Худшая производительность
Лучшая производительность
Наихудшая пространственная сложность	вспомогательный
Оптимальный	Да

В информатике медиана медиан — это приблизительный алгоритм медианного выбора , часто используемый в качестве хорошей опорной точки для точного алгоритма выбора, чаще всего быстрого выбора , который выбирает k -й наименьший элемент изначально неотсортированного массива. Медиана медиан находит приблизительную медиану за линейное время. Используя эту приблизительную медиану в качестве улучшенного опорного элемента, сложность быстрого выбора в наихудшем случае снижается с квадратичной до линейной , что также является асимптотически оптимальной сложностью в наихудшем случае для любого алгоритма выбора. Другими словами, медиана медиан — это приблизительный алгоритм выбора медианы, который помогает построить асимптотически оптимальный, точный общий алгоритм выбора (особенно в смысле сложности наихудшего случая), создавая хорошие опорные элементы.

Медиану медиан также можно использовать в качестве стратегии поворота в быстрой сортировке , что дает оптимальный алгоритм со сложностью в наихудшем случае. $O(n\log n)$ . ^{[ нужна ссылка ]} Хотя этот подход довольно хорошо оптимизирует асимптотическую сложность наихудшего случая, на практике он обычно проигрывает, если вместо этого выбирать случайные повороты для своего среднего значения. $O(n)$ сложность для выбора и средняя $O(n\log n)$ сложность сортировки без каких-либо затрат на вычисление опорной точки.

Аналогичным образом, медиана медиан используется в гибридном алгоритме интроселекта в качестве запасного варианта для поворотного выбора на каждой итерации до тех пор, пока не будет найдено k-е наименьшее значение. Это снова обеспечивает линейную производительность в наихудшем случае в дополнение к линейной производительности в среднем случае: вводный выбор начинается с быстрого выбора (со случайным поворотом, по умолчанию), чтобы получить хорошую среднюю производительность, а затем возвращается к модифицированному быстрому выбору с поворотом, полученным из медианы медианы, если прогресс слишком медленный. Несмотря на асимптотическое сходство, такой гибридный алгоритм будет иметь меньшую сложность, чем прямой интроселект, с точностью до постоянного коэффициента (как в среднем, так и в худшем случае) при любой конечной длине.

Алгоритм был опубликован в Blum et al. (1973) и поэтому иногда называется БФПРТ по фамилиям авторов. В исходной статье алгоритм назывался PICK , а быстрый выбор назывался «FIND».

Мотивация

Быстрый выбор в среднем занимает линейное время, но при неудачном выборе поворота может потребоваться квадратичное время. Это связано с тем, что быстрый выбор — это алгоритм «разделяй и властвуй» , в котором каждый шаг занимает $O(n)$ время в размере оставшегося набора поиска. Если набор поиска экспоненциально быстро уменьшается в размерах (по фиксированной пропорции), это дает геометрическую серию, умноженную на $O(n)$ коэффициент одного шага и, следовательно, линейное общее время. Однако если набор поиска уменьшается в размере медленно, например линейно (на фиксированное число элементов, в худшем случае каждый раз уменьшаясь только на один элемент), то линейная сумма линейных шагов дает квадратичное общее время (формально, треугольное) . цифры растут квадратично). Например, худший случай возникает при повороте наименьшего элемента на каждом этапе, например, при применении быстрого выбора для максимального элемента к уже отсортированным данным и каждый раз взятии первого элемента в качестве поворота.

Если вместо этого последовательно выбирать «хорошие» опорные точки, этого можно избежать и всегда получать линейную производительность даже в худшем случае. «Хороший» опорный элемент — это тот, для которого мы можем установить, что постоянная пропорция элементов попадает как ниже, так и выше него, поскольку тогда набор поиска уменьшается, по крайней мере, на постоянную пропорцию на каждом шаге, следовательно, экспоненциально быстро, а общее время остается линейный. Медиана — это хороший ориентир — лучший для сортировки и лучший общий выбор для выбора — уменьшающий набор поиска вдвое на каждом этапе. Таким образом, если можно вычислить медиану за линейное время, это только добавит линейное время к каждому шагу, и, таким образом, общая сложность алгоритма останется линейной.

Алгоритм медианы медиан вычисляет приблизительную медиану, а именно точку, которая гарантированно находится между 30-м и 70-м процентилями (в средних 4 децилях ). Таким образом набор поиска уменьшается как минимум на 30%. Задача уменьшена до 70 % от исходного размера, что на фиксированную пропорцию меньше. Рекурсивное применение того же алгоритма к уже меньшему множеству до тех пор, пока не останется только один или два элемента, приводит к затратам ${\frac {n}{1-0.7}}\approx 3.33{n}$

Алгоритм

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

function nthSmallest(list, n)
    index := select(list, 1, length of list, n) // Use select(list, 0, length of list - 1, n - 1) if list is zero-based numbering
    return list[index]

Будьте осторожны при обращении left, right и n при реализации. Следующий псевдокод предполагает, что left, right, и в списке используется нумерация, начинающаяся с единицы, и это select первоначально вызывается с 1 в качестве аргумента left и длина списка в качестве аргумента right. Обратите внимание, что после перестановки списка возвращается индекс n-го наименьшего числа, а не фактическое значение n-го наименьшего числа.

function select(list, left, right, n)
    loop
        if left = right then
            return left
        pivotIndex := pivot(list, left, right)
        pivotIndex := partition(list, left, right, pivotIndex, n)
        if n = pivotIndex then
            return n
        else if n < pivotIndex then
            right := pivotIndex - 1
        else
            left := pivotIndex + 1

Подпрограмма Pivot — это фактический алгоритм медианы медиан. Он делит входные данные (список длины $n$ ) на группы, состоящие не более чем из пяти элементов, вычисляет медиану каждой из этих групп с помощью некоторой подпрограммы, а затем рекурсивно вычисляет истинную медиану ${\frac {n}{5}}$ медианы, найденные на предыдущем шаге: ^[1] Обратите внимание, что сводные звонки выбирать ; это пример взаимной рекурсии .

function pivot(list, left, right)
    // for 5 or less elements just get median
    if right − left < 5 then
        return partition5(list, left, right)
    // otherwise move the medians of five-element subgroups to the first n/5 positions
    for i from left to right in steps of 5
        // get the median position of the i'th five-element subgroup
        subRight := i + 4
        if subRight > right then
            subRight := right
        median5 := partition5(list, i, subRight)
        swap list[median5] and list[left + floor((i − left) / 5)]

    // compute the median of the n/5 medians-of-five
    mid := floor((right − left) / 10) + left + 1
    return select(list, left, left + floor((right − left) / 5), mid)

Вспомогательные функции разделов

Есть подпрограмма под названием раздел , который может за линейное время группировать список (начиная от индексов left к right) на три части: те, которые меньше определенного элемента, те, которые равны ему, и те, которые больше этого элемента ( трехстороннее разбиение ). Группировка на три части гарантирует, что медиана медиан сохраняет линейное время выполнения в случае многих или всех совпадающих элементов. Вот псевдокод, который выполняет разбиение элемента list[pivotIndex]:

function partition(list, left, right, pivotIndex, n)
    pivotValue := list[pivotIndex]
    swap list[pivotIndex] and list[right]  // Move pivot to end
    storeIndex := left
    // Move all elements smaller than the pivot to the left of the pivot
    for i from left to right − 1 do
        if list[i] < pivotValue then
            swap list[storeIndex] and list[i]
            increment storeIndex
    // Move all elements equal to the pivot right after
    // the smaller elements
    storeIndexEq := storeIndex
    for i from storeIndex to right − 1 do
        if list[i] = pivotValue then
            swap list[storeIndexEq] and list[i]
            increment storeIndexEq
    swap list[right] and list[storeIndexEq]  // Move pivot to its final place
    // Return location of pivot considering the desired location n
    if n < storeIndex then
        return storeIndex  // n is in the group of smaller elements
    if n ≤ storeIndexEq then
        return n  // n is in the group equal to pivot
    return storeIndexEq // n is in the group of larger elements

The Функция раздела5 выбирает медиану группы, состоящей не более чем из пяти элементов; простой способ реализовать это — сортировка вставками , как показано ниже. ^[1] Его также можно реализовать в виде дерева решений .

function partition5(list, left, right)
    i := left + 1
    while i ≤ right do
        j := i
        while j > left and list[j−1] > list[j] do
            swap list[j−1] and list[j]
            j := j − 1
        i :=  i + 1

    return left + (right - left) / 2

Свойства точки поворота

Принадлежащий ${\frac {n}{5}}$ группы, половина количества групп $\left({\frac {1}{2}}\times {\frac {n}{5}}={\frac {n}{10}}\right)$ имеют медиану меньше, чем ось (медиана медиан). Кроме того, еще половина количества групп $\left({\text{again, }}{\frac {1}{2}}\times {\frac {n}{5}}={\frac {n}{10}}\right)$ имеют медиану больше, чем ось. В каждом из ${\frac {n}{10}}$ В группах с медианой меньше опорной точки есть два элемента, которые меньше соответствующих медиан, которые меньше опорной точки. Таким образом, каждый из ${\frac {n}{10}}$ группы имеют как минимум 3 элемента, меньшие, чем опорная точка. Аналогично в каждом из ${\frac {n}{10}}$ В группах с медианой, большей, чем ось, есть два элемента, которые превышают соответствующие медианы, которые больше, чем ось. Таким образом, каждый из ${\frac {n}{10}}$ группы имеют как минимум 3 элемента, которые больше опорной точки. Следовательно, ось меньше $3\times {\frac {n}{10}}$ элементы и больше другого $3\times {\frac {n}{10}}$ элементы. Таким образом, выбранная медиана разделяет упорядоченные элементы где-то между 30%/70% и 70%/30%, что обеспечивает линейное поведение алгоритма в худшем случае. Чтобы визуализировать:

Одна итерация рандомизированного набора из 100 элементов от 0 до 99.
	12	15	11	2	9	5	0	7	3	21	44	40	1	18	20	32	19	35	37	39
	13	16	14	8	10	26	6	33	4	27	49	46	52	25	51	34	43	56	72	79
медианы	17	23	24	28	29	30	31	36	42	47	50	55	58	60	63	65	66	67	81	83
	22	45	38	53	61	41	62	82	54	48	59	57	71	78	64	80	70	76	85	87
	96	95	94	86	89	69	68	97	73	92	74	88	99	84	75	90	77	93	98	91

(красный = «(один из двух возможных) медиан медиан», серый = «число <красный», белый = «число > красный»)

Для ясности здесь показаны 5-кортежи, отсортированные по медиане. Сортировка кортежей не требуется, поскольку нам нужна только медиана для использования в качестве элемента поворота.

Обратите внимание, что все элементы выше/слева от красного (30% от 100 элементов) меньше, а все элементы ниже/справа от красного (еще 30% от 100 элементов) больше.

Доказательство линейного времени работы

Рекурсивный вызов с вычислением медианы не превышает линейного поведения в худшем случае, поскольку список медиан имеет размер ${\frac {n}{5}}$ , в то время как другой рекурсивный вызов рекурсивно обрабатывает не более 70% списка. Позволять $T(n)$ это время, необходимое для запуска алгоритма быстрого выбора медианы медиан для массива размером $n$ . Тогда мы знаем, что на этот раз:

T(n)\leq T(n/5)+T(n\cdot 7/10)+c\cdot n,

где

тот $T\left({\frac {n}{5}}\right)$ часть предназначена для нахождения истинной медианы ${\frac {n}{5}}$ медианы, запустив для них (независимый) быстрый выбор (поскольку поиск медианы - это всего лишь частный случай выбора k -наименьшего элемента)
тот $O(n)$ срок $c\cdot n$ заключается в работе по разделению для создания двух сторон, одна из которых будет рекурсивной в нашем быстром выборе (мы посещали каждый элемент постоянное количество раз, чтобы сформировать их в группы n/5 и взять каждую медиану в $O(1)$ время).
тот $T\left({\frac {7n}{10}}\right)$ часть предназначена для фактической рекурсии Quickselect (в худшем случае, когда k -й элемент находится в большем разделе, который может иметь размер ${\frac {7n}{10}}$ максимально)

По индукции:

T(n)\leq 10\cdot c\cdot n\in O(n).

Анализ

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

Конкретный выбор групп из пяти элементов объясняется следующим. Во-первых, вычисление медианы нечетного списка происходит быстрее и проще; хотя можно использовать четный список, для этого потребуется взять среднее значение двух средних элементов, что медленнее, чем простой выбор одного точного среднего элемента. Во-вторых, пять — это наименьшее нечетное число, для которого работает медиана из медиан. Если группы состоят всего из трех элементов, результирующий список медиан для поиска имеет длину. ${\frac {n}{3}}$ и сокращает список до рекурсивного размера ${\frac {2}{3}}n$ , поскольку оно больше 1/2 × 2/3 = 1/3 элементов и меньше 1/2 × 2/3 = 1/3 элементов. Таким образом, это все еще оставляет $n$ элементы для поиска, не уменьшая проблему в достаточной степени. Однако отдельные списки короче, и результирующую сложность можно связать с $O(n\log n)$ по методу Акры–Бацци , но это не доказывает линейности.

И наоборот, вместо этого можно сгруппировать по $g$ = семь, девять или более элементов, и это работает. Это уменьшает размер списка медиан до ${\frac {n}{g}}$ , а размер списка для рекурсии в асимптоты составляет 3 n /4 (75%), поскольку квадранты в приведенной выше таблице приближаются к 25%, поскольку размер перекрывающихся линий уменьшается пропорционально. Это асимптотически уменьшает масштабный коэффициент с 10 до 4, но соответственно увеличивает $c$ срок выполнения работ по разделению. Нахождение медианы для более крупной группы занимает больше времени, но является постоянным фактором (зависящим только от $g$ ), и, таким образом, не меняет общую производительность по мере роста n . Фактически, учитывая количество сравнений в худшем случае, постоянный коэффициент равен ${\frac {2g(g-1)}{g-3}}$ .

Если вместо этого кто-то группирует по-другому, скажем, разделив $n$ список элементов на 5 списков, вычисление медианы каждого, а затем вычисление медианы из них – т. е. группировка по постоянной дроби, а не по постоянному числу – это не так явно уменьшает проблему, поскольку для этого требуется вычислить 5 медиан, каждый в списке ${\frac {n}{5}}$ элементов, а затем рекурсивно использовать список длиной не более ${\frac {7}{10}}n$ . Как и в случае с группировкой по 3, отдельные списки короче, но общая длина не короче – на самом деле больше – и, таким образом, можно доказать только суперлинейные границы. Группируемся в квадрат ${\sqrt {n}}$ списки длины ${\sqrt {n}}$ так же сложен.