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

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

Медиана медиан
Учебный класс	Алгоритм выбора
Структура данных	Множество
Наихудшая производительность	${\ Displaystyle О (п)}$
Лучшая производительность	${\ Displaystyle О (п)}$
Сложность пространства в наихудшем случае	${\ Displaystyle О (\ журнал п)}$ вспомогательный

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

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

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

Алгоритм был опубликован в Blum et al. (1973) , и поэтому иногда называется BFPRT по фамилиям авторов. В исходной статье алгоритм назывался PICK , а quickselect - «НАЙТИ».

Мотивация [ править ]

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

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

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

Алгоритм [ править ]

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

функция select (list, left, right, n) цикл,  если left = right, то  возврат влево pivotIndex: = pivot (список, слева, справа) pivotIndex: = partition (список, слева, справа, pivotIndex, n) если n = pivotIndex, тогда  вернуть n иначе, если n <pivotIndex, то справа: = pivotIndex - 1 еще слева: = pivotIndex + 1

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

функциональный раздел (список, слева, справа, pivotIndex, n) pivotValue: = список [pivotIndex] swap list [pivotIndex] and list [right] // Переместить сводку в конец storeIndex: = left // Переместить все элементы меньшие , чем стержень влево от оси  для I от налево на право - 1 делать ,  если список [я] <pivotValue затем список подкачки [storeIndex] и список [i] инкремент storeIndex // Перемещаем все элементы, равные оси поворота, сразу после  // меньших элементов storeIndexEq = storeIndex для I от storeIndex в порядке - 1 делать ,  если список [я] = pivotValue тогда список подкачки [storeIndexEq] и список [i] инкремент storeIndexEq swap list [right] и list [storeIndexEq] // Переместить точку поворота в ее последнее место // Вернуть местоположение точки поворота с учетом желаемого местоположения n,  если n <storeIndex, затем  вернуть storeIndex // n находится в группе меньших элементов,  если n ≤ storeIndexEq затем  return n // n находится в группе, равной pivot  return storeIndexEq // n находится в группе более крупных элементов

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

function pivot (list, left, right) // для 5 или менее элементов просто получить медианное значение,  если right - left <5, затем  вернуть partition5 (list, left, right) // в противном случае переместите медианы пятиэлементных подгрупп в первые n / 5 позиций  для I от налево на правый с шагом 5 // получить срединную позицию i - ой пятиэлементной подгруппы subRight: = i + 4 если subRight> право, то subRight: = право median5: = partition5 (список, i, subRight) список подкачки [median5] и список [left + floor ((i - left) / 5)] // вычисляем медиану n / 5 медиан из пяти середина: = (справа - слева) / 10 + слева + 1 return select (list, left, left + floor ((right-left) / 5), mid)

Partition5 подпрограмма выбирает медиану группы не более пяти элементов; простой способ реализовать это - сортировка вставкой , как показано ниже. ^[1] Его также можно реализовать в виде дерева решений .

функция partition5 (список, слева, справа) i: = left + 1 в то время как я ≤ правый j: = я в то время как j> left и list [j − 1]> list [j] do список подкачки [j − 1] и список [j] j: = j - 1 я: = я + 1  обратный этаж ((левый + правый) / 2)

Свойства pivot [ править ]

Из п / 5 групп, половина числа групп (½ × п / 5 = п / 10) имеет свою медиану меньше , чем стержень (алгоритм выбора). Кроме того, у другой половины групп (опять же, ½ × n / 5 = n / 10) медиана больше, чем точка поворота. В каждой из n / 10 групп с медианой меньше, чем точка поворота, есть два элемента, которые меньше, чем их соответствующие медианы, которые меньше, чем точка поворота. Таким образом, каждая из n / 10 групп имеет по крайней мере 3 элемента, которые меньше стержня. Аналогично в каждом из n/ 10 групп с медианой больше, чем точка поворота, есть два элемента, которые больше, чем их соответствующие медианы, которые больше, чем точка поворота. Таким образом, каждая из n / 10 групп имеет как минимум 3 элемента, которые больше стержня. Следовательно, точка поворота меньше 3 ( n / 10) элементов и больше, чем еще 3 ( 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 элементов) больше.

Доказательство времени работы O ( n ) [ править ]

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

{\ Displaystyle Т (п) \ Leq Т (п / 5) + Т (п \ CDOT 7/10) + с \ CDOT п.}

куда

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

Отсюда с помощью индукции легко показать, что

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

Анализ [ править ]

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

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

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

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

Ссылки [ править ]

^ а б Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03384-4.

Блюм, М .; Флойд, RW ; Пратт, В.Р . ; Ривест, Р.Л . ; Тарьян, Р. Э. (август 1973 г.). «Сроки выбора» (PDF) . Журнал компьютерных и системных наук . 7 (4): 448–461. DOI : 10.1016 / S0022-0000 (73) 80033-9 .CS1 maint: ref=harv (link)

Внешние ссылки [ править ]

« Конспект от 30 января 1996 г .: Детерминированный выбор », ICS 161: Разработка и анализ алгоритмов, Дэвид Эппштейн.

[clrs-1] а б Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03384-4.

[1]