что такое медиана массива

Что такое медиана массива

Блог пользователя slalex

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

Задача такова, что необходимо найти медиану массива (неотсортированного конечно же).
Т.е. такое значение, которое после сортировки массива A[1. n] будет равно:
элементу A[n / 2 + 1], при нечетном n и (A[n / 2] + A[n / 2 + 1]) / 2.0, при четном n.

НО. самое интересное, что алгоритм должен быть линейным. 8)

Источник

Золотая середина. Поиск медианного элемента потока входных чисел

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

Постановка задачи

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

Медиана ряда чисел

Либо можно выбирать элемент под номером , если чётное и если нечетное.

Наивный подход

Давайте обсудим бейзлайновое решение, при котором медиану можно получить за .

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

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

Улучшить этот результат нам поможет структура данных — куча.

Куча. Min-heap, max-heap

Рассмотрим кучу на примере min-heap. Min-heap — это бинарное дерево, обладающее двумя следующими свойствами:

Аналогично образом задаётся max-heap, нужно заменить «меньше» на «больше» в первом свойстве.
При решении задачи мы хотим воспользоваться операциями, которые благодаря построению кучи, могут быть выполнены быстрее, чем за линейное время.

Первая из этих операций: взятие минимума (максимума) и удаление

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

Метод extract внутри себя запускает следующий процесс: сначала элемент с самого последнего уровня ставится в корень дерева, затем на корне дерева стартует метод bubble_down, который уровень за уровнем (а таких всего в полном дереве) опускает новый корневой узел.
Код реализации на языке Python смотри ниже.

Вторая операция: добавление элемента

Чтобы добавить произвольный элемент в кучу требуется выставить новый элемент на правильное место, не утратив 2 свойства кучи. Для этого новый элемент добавляется на последний уровень, а затем методом bubble_up поднимается в сторону корня, пока над ним не окажется элемент меньший него или он не станет корнем. Сложность этой операции также равна

Код, в котором мы определим необходимую функциональность с возможностью определения min и max-heap:

Оптимальное решение

Теперь перейдем непосредственно к реализации алгоритма контроля медианы, основанном на использовании кучи. Мы будем использовать две кучи, одну минимальную, другую максимальную. Идея заключается в следующем: давайте разделим поток значений на верхнюю часть, содержащую большие значения и нижнюю, содержащую меньшие значения. Первую реализуем на основе min-heap, чтобы легко получать минимальный элемент, который лежит на разделе, а вторую на основе max-heap.

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

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

Заключение

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

В преддверии старта курса «Алгоритмы и структуры данных» приглашаем всех желающих на бесплатный двухдневный интенсив по теме: Алгоритм сжатия данных — код Хаффмана.

Источник

Мой любимый алгоритм: нахождение медианы за линейное время

Нахождение медианы за O(n log n)

У этого способа самый простой код, но он определённо не самый быстрый.

Нахождение медианы за среднее время O(n)

Следующим нашим шагом будет нахождение медианы в среднем за линейное время, если нам будет везти. Этот алгоритм, называемый «quickselect», разработан Тони Хоаром, который также изобрёл алгоритм сортировки с похожим названием — quicksort. Это рекурсивный алгоритм, и он может находить любой элемент (не только медиану).

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

Доказательство среднего времени O(n)

В среднем pivot разбивает список на две приблизительно равных части. Поэтому каждая последующая рекурсия оперирует с 1 ⁄₂ данных предыдущего шага.

Существует множество способов доказательства того, что этот ряд сходится к 2n. Вместо того, чтобы приводить их здесь, я сошлюсь на замечательную статью в Википедии, посвящённую этому бесконечному ряду.

Quickselect даёт нам линейную скорость, но только в среднем случае. Что, если нас не устраивает среднее, и мы хотим гарантированного выполнения алгоритма за линейное время?

Детерминированное O(n)

С учётом этого, нам нужен алгоритм для подбора опорных элементов. Нашей целью будет выбор за линейное время pivot, который в худшем случае удаляет достаточное количество элементов для обеспечения скорости O(n) при использовании его вместе с quickselect. Этот алгоритм был разработан в 1973 году Блумом (Blum), Флойдом (Floyd), Праттом (Pratt), Ривестом (Rivest) и Тарьяном (Tarjan). Если моего объяснения вам не хватит, то можете изучить их статью 1973 года. Вместо того, чтобы описывать алгоритм, я подробно прокомментирую мою реализацию на Python:

Давайте докажем, что медиана медиан является хорошим pivot. Нам поможет, если мы представим визуализацию нашего алгоритма выбора опорных элементов:

Но достаточно ли нам отбрасывать 30% элементов на каждом этапе? На каждом этапе наш алгоритм должен выполнять следующее:

Подводим итог

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

Медианы за линейное время на практике

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

Именно этого мы и ожидали! Детерминированный опорный элемент почти всегда рассматривает при quickselect меньшее количество элементов, чем случайный. Иногда нам везёт и мы угадываем pivot с первой попытки, что проявляется как впадины на зелёной линии. Математика работает!

Источник

Русские Блоги

Медиана двух отсортированных массивов

Перевод с: https://blog.csdn.net/hk2291976/article/details/51107778

Введение в проблему

Это классический алгоритм «разделяй и властвуй»! Этот вопрос примерно относится к тому, как найти среднее значение в данных двух упорядоченных массивах или к проблеме деформации, как найти значение Top K в двух упорядоченных массивах (проблема Top K может быть преобразована в поиск Проблема k-го элемента).

Потому что он удален слева от медианы x x Число, исключенное справа x x Медиана оставшегося массива остается исходной медианой.

Исходя из приведенных выше правил, алгоритм может быть получен:

Необходимые знания

Сначала объясните «разрез»

Мы можем вырезать Аккуратный Массив разделен на левую и правую части.Разрез называется Cut.Слева и справа от разреза будут два элемента: максимальное значение слева и минимальное значение справа.

Мы определяем L = Max (LeftPart), R = Min (RightPart)

Ps. Разрез можно разрезать между двумя числами или на одно число.Если разрезать на одно число, то число принадлежит левой и правой. (Я расскажу об этом позже, когда буду говорить о среднем значении отдельного массива)

Например, для последовательности [2 3 5 7] разрез находится между 3 и 5.
[2 3 / 5 7]
Медиана равна (3 + 5) / 2 = 4

Если последовательность [2 3 4 5 6] разрезана на 4, мы можем разделить 4 на 2
[2 3 (4/4) 5 7]
Медиана равна (4 + 4) / 2 = 4

Таким образом можно гарантировать, что независимо от того, является ли медианное значение 1 числом или 2 числами, оно может работать единообразно.

Вырезать и k-й элемент

Здравый смысл 1: Если разрезать в позиции k, то A [k] будет L. Другими словами, если слева есть k элементов, A [k] принадлежит максимальному значению левой части. (Это все очевидные вещи, не нужно это объяснять!)

Двойной массив

Мы устанавливаем:
C i Ci Срез i-го массива. Чтобы
L i Li Левый элемент после разреза i-го массива.
R i Ri Правый элемент после разреза i-го массива.

Как извлечь k-й элемент из массива double

Предполагая, что k = 3

За
[ 1 4 7 9 ] [1 4 7 9]
[ 2 3 5 ] [2 3 5]

Установите C1 = 2, тогда C2 = k-C1 = 1
[ 1 4 / 7 9 ] [1 4/7 9]
[ 2 / 3 5 ] [2/3 5]

Если в приведенном выше примере Изменение k на 4 и есть среднее значение.

Давайте рассмотрим среднюю проблему особых обстоятельств более подробно ниже.

Четность двойного массива

Сделайте массив всегда нечетным

Есть ли способ увеличить длину двух массивов до нечетного или четного числа?

Фактически, виртуальный Добавьте «#» (этот трюкалгоритм манахераОн также применяется в), так что длина массива всегда является нечетным числом (2n + 1 всегда является нечетным числом). Чтобы
Ps. Обратите внимание, что это виртуальное добавление, на самом деле такого шага нет вообще, потому что с помощью следующего преобразования мы можем гарантировать, что каждый элемент после виртуального добавления соответствует исходному элементу один к одному

Отображение отношений

В чем преимущество этого, зачем вы его добавляете? Потому что после этого добавления Каждая позиция может пройти / 2, чтобы получить позицию исходного элемента.

Представляет «разрез» в виртуальном массиве

Кроме того, его легче разрезать. Если разрезание по «#» означает разрезание между двумя элементами, разрезание по числам равносильно разделению чисел на 2 части.

Удивительно то, что в любом случае:

пример:
1. Разрезать между 4/7 ‘#’, C = 4, L = (4-1) / 2 = 1, R = 4/2 = 2
Это исходная позиция 4 и 7! Чтобы
2. Вырезать на 3, C = 3, L = (3-1) / 2 = 1, R = 3/2 = 1, что является позицией 3!

С остальным легко справиться. Думайте о двух массивах как о виртуальном массиве A, в настоящее время существует 2m + 2n + 2 элемента, разрезанных на m + n + 1, поэтому нам нужно только найти m + n + 1 Подойдет элемент position и элемент position m + n + 2. Чтобы
Слева: A [m + n + 1] = Макс (L1 + L2)
Справа: A [m + n + 2] = Min (R1 + R2)

Что касается схемы поиска разрезов в двух массивах, то это схема выше.

Разделяй и властвуй

С учетом вышеизложенного вопрос теперь в том, как использовать идею «разделяй и властвуй».

Как разделить?

Как вылечить?

Трансграничные вопросы

Что делать, если C1 или C2 закончились? Чтобы
Такая ситуация возникает: Если массив полностью меньше или больше медианы. Возможны 4 ситуации:
— C1 = 0 —— Общий массив 1 больше медианы, L1> R2, а медиана находится в 2.
— C2 = 0 —— Весь массив 1 меньше медианного значения L1

Источник

Что такое медиана массива

Блог пользователя slalex

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

Задача такова, что необходимо найти медиану массива (неотсортированного конечно же).
Т.е. такое значение, которое после сортировки массива A[1. n] будет равно:
элементу A[n / 2 + 1], при нечетном n и (A[n / 2] + A[n / 2 + 1]) / 2.0, при четном n.

НО. самое интересное, что алгоритм должен быть линейным. 8)

Источник