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

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

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

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

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

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

Источник

Поиск медианного значения массива?

Мне было интересно, можно ли найти медианное значение массива? Например, предположим, что у меня есть массив девятого размера. Можно ли найти средний слот этого массива?

8 ответов

предполагая, что массив x сортируется и имеет длину n:

Если n нечетно, то медиана равна x [(n-1)/2].
Если n четное, чем медиана (x[n / 2] + x[(n/2)-1]) / 2.

Если вы хотите использовать любые внешние библиотеки Apache commons math library используя Вы можете рассчитать в среднем.
Для получения дополнительных методов и использования посмотрите на документация по API

рассчитать в программе

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

Это очень просто, так как у вас есть 9 элементов (нечетное число).
Найдите средний элемент массива.
В вашей программе вы можете объявить array

затем нужно отсортировать массив, используя массивы#вроде

это возможно потому, что в Java массивы имеют фиксированный размер.

ресурсы :

ответ Java выше работает только в том случае, если есть нечетное количество чисел, вот ответ, который я получил к решению:

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

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

реализация немного сложно получить право, но вот пример, который опирается на Comparable интерфейс и Collections.shuffle() без каких-либо внешних зависимостей.

код производит следующую статистику заказа для этих входных данных массивы:

Источник

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

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

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

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

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

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

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

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

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

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

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

Куча. 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 с первой попытки, что проявляется как впадины на зелёной линии. Математика работает!

Источник

медиана

Медиана является средним значением набора данных. Чтобы определить медианное значение в последовательности чисел, числа сначала должны быть расположены в порядке возрастания.

Факт о Медиане:

Формула медианы несгруппированных данных:

Формула медианы сгруппированных данных:

Как найти медиану несортированного массива?

Наивное решение:
Учитывая размер несортированного массива, найдите его медиану.

Median of a sorted array of size n is defined as below :

It is middle element when n is odd and average of middle two elements when n is even. Since the array is not sorted here, we sort the array first, then apply above formula.

Примеры:

Ниже приведена реализация кода:

// Программа CPP для поиска медианы
#include

using namespace std;

// Функция для вычисления медианы

double findMedian( int a[], int n)

// Сначала сортируем массив

// проверяем четный случай

return ( double )a[n / 2];

int n = sizeof (a) / sizeof (a[0]);

// Java программа для поиска медианы

// Функция для вычисления медианы

public static double findMedian( int a[], int n)

// Сначала сортируем массив

// проверяем четный случай

return ( double )a[n / 2 ];

public static void main(String args[])

System.out.println( «Median = » + findMedian(a, n));

# Python3 программа для поиска медианы

# Функция для вычисления медианы

# Сначала мы сортируем массив

# проверить четный случай

return float (a[n / 2 ])

// C # программа для поиска медианы

public static double findMedian( int [] a, int n)

// Сначала мы сортируем

return ( double )a[n / 2];

public static void Main()

Console.Write( «Median = » + findMedian(a, n) + «\n» );

// PHP программа для поиска медианы

// Функция для
// вычисление медианы

// Сначала сортируем массив

// проверяем четный случай

Выход:

Основная программа, связанная с медианой:

Больше проблем, связанных с медианой:

Источник