Медиана ряда чисел
Если в числовом ряде есть дробные числа, используйте точку для их записи. Например, 0.42, 0.55.
Как найти медиану ряда чисел
Чтобы разобраться, как находить медиану ряда чисел, мы рассмотрим несколько примеров.
Пример 1. Найти медиану числового ряда
Решение. Записываем все числа ряда в порядке возрастания: . Количество чисел в ряду чётно, поэтому медиана этого ряда будет равна полусумме двух средних чисел: .
Пример 2. Найти медиану числового ряда
Решение. записываем все числа ряда в порядке возрастания: . Количество чисел в ряду нечётно, поэтому медиана этого ряда будет равна стоящему посередине числу, то есть равна .
Золотая середина. Поиск медианного элемента потока входных чисел
В этой статье мы рассмотрим следующую задачу: поиск и поддержание медианы среди целых чисел, которые последовательно попадают на обработку. В этом посте мы поставим задачу, разберём все необходимые вводные, предложим и оценим сложность решения.
Постановка задачи
На вход алгоритму подаётся поток целых чисел, т.е. количество чисел может быть неизвестно, но мы будем считать, что массив задан наперёд и его длина очень большая. Требуется разработать алгоритм, который определяет медиану текущего массива, т.е. считанного из исходного к данному моменту. При этом требуется, чтобы сложность такого алгоритма была
Медиана ряда чисел
Либо можно выбирать элемент под номером , если чётное и если нечетное.
Наивный подход
Давайте обсудим бейзлайновое решение, при котором медиану можно получить за .
Пусть каждое новое число из потока мы будем вставлять в массив так, чтобы массив оставался упорядоченным. Затем будем выбирать элемент из середины и добавлять его в список медиан.
Как упоминалось выше, этот алгоритм будет иметь квадратичную сложность, поскольку для каждого из элементов потока, мы выполняем линейную работу по поиску места и вставке элемента в массив.
Улучшить этот результат нам поможет структура данных — куча.
Куча. 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.
Всякий раз, когда мы читаем из потока очередное число, будем добавлять его в верхнюю часть, если оно больше наименьшего из этой половины и в нижнюю часть, если верно обратное. Затем, осуществив вставку, будем балансировать две части, чтобы они содержали по половине из введенных значений.
Каждую итерацию внешнего цикла, мы делаем несколько шагов сложностью , посколько операции вставки и получения элемента из кучи ограничены этой сложностью. По этой причине итоговая сложность не превышает .
Заключение
В этой статье на примере задачи мы обсудили преимущества кучи по сравнению со списком. Познакомились с временной сложностью операций над этой структурой данных. Реализовали код этой структуры, необходимый для эффективного выполнения задачи по поиску медианного элемента в потоке чисел.
В преддверии старта курса «Алгоритмы и структуры данных» приглашаем всех желающих на бесплатный двухдневный интенсив по теме: Алгоритм сжатия данных — код Хаффмана.
Медиана чисел
Онлайн калькулятор для нахождения медианы ряда чисел. Медианой (серединой) набора чисел называется число стоящее посередине упорядоченного по возрастанию ряда чисел. Если количество чисел в ряду чётное, то медианой ряда является полусумма двух стоящих посередине чисел. Применяется в математической статистике — число, характеризующее выборку (например, набор чисел), также используется для вычисления медианной зарплаты.
Формула медианы числового набора, пример вычисления медианы числового ряда: 3, 7, 1, 6, 9
Решение: упорядочиваем список чисел в порядке возрастания: 1, 3, 6, 7, 9. Поскольку количество чисел в ряду нечётное, то число 6 стоящее по середине и будет являться медианой данного ряда.
Пример нахождения медианы ряда чисел: 1, 5, 8, 4, 3, 9
Решение: записываем все числа ряда в порядке возрастания: 1, 3, 4 ,5, 8, 9. Поскольку чисел в ряду чётное, то медиана этого ряда будет равна полусумме двух средних чисел: (4+5)/2 = 4.5
Почему для анализа лучше использовать медианные значения, а не средние
Что такое среднее значение и почему оно не всегда корректно
Когда мы имеем дело со статистическими данными, их нужно как‑то структурировать. Сами по себе демографические и экономические показатели, такие как зарплата и продолжительность жизни, оценки, баллы и многое другое, представляют собой лишь беспорядочный массив чисел.
Чтобы привести их к порядку, можно использовать среднее арифметическое значение. Для этого надо сложить все числа и разделить на количество слагаемых:
И хотя среднее арифметическое легко посчитать, у него есть серьёзный недостаток: если один показатель сильно отличается от остальных, то он серьёзно искажает итоговый результат. Ситуацию хорошо описывает анекдот: «Чиновники едят мясо, а я — капусту. В среднем мы едим голубцы».
Среднее арифметическое может быть значительно больше или меньше большинства чисел. Так, в ряду «1, 2, 1, 1, 3, 8, 10, 1, 587» оно окажется равным 68,2. А если в общий расчёт попадёт девять человек со сбережениями в 100 тысяч рублей и один банкрот с полумиллионным долгом, средняя сумма накоплений составит 40 тысяч.
Проще говоря, среднее арифметическое может не отражать действительности.
Что такое медиана и чем она лучше
Чтобы застраховаться от подобных ошибок, вместо среднего значения можно применять медианное.
Медиана поможет найти именно тот показатель, который ближе всего к истинно среднему. На неё не влияют выбивающиеся из общей массы числа, поэтому она считается одним из самых надёжных и устойчивых показателей. Так, для упомянутого выше ряда «1, 2, 1, 1, 3, 8, 10, 1, 587» медиана будет равна 2. Если вместо 587 поставить 87, она всё равно будет равна 2, если 7 — тоже 2. Среднее арифметическое же в аналогичных случаях будет меняться: 12,7 и 3,8 соответственно.
С помощью медианы можно получить более точные данные и правильнее интерпретировать статистику. Например, при расчёте средней заработной платы, когда 19 сотрудников получают по 20 тысяч рублей, а директор — миллион. Среднее арифметическое в этом случае будет равным 69 тысячам рублей, а медиана — 20. Поэтому последнюю и предпочитают люди, работающие с цифрами: от бухгалтеров до учёных.
Медианное значение рассчитывается из числа или пары чисел, которые больше одной половины показателей и меньше другой. Чтобы найти медиану, надо упорядочить набор чисел и просто найти в нём середину. Вот так: «1, 1, 1, 1, 2, 3, 8, 10, 587».
Если в ряде чётное количество показателей, как например в «1, 1, 1, 1, 2, 3, 8, 10», надо взять два средних числа. Это 1 и 2. Их нужно сложить, а сумму разделить пополам:
Как посчитать медиану, когда данных много
В таком случае можно воспользоваться специальными инструментами.
Онлайн
Например, на сайте Calculator Soup. Достаточно скопировать данные в нужное окно и нажать на кнопку «Calculate». Помимо медианы, калькулятор сразу высчитает кучу других вещей: среднее арифметическое, минимальное и максимальное значение, количество показателей, общую сумму и так далее.
Скриншот: Calculator Soup
Excel
В редакторе таблиц есть функция «Медиана». Достаточно найти её в специальном окне и выделить массив данных, чтобы высчитать показатель. То же самое можно сделать в Google Docs.
Есть ли альтернативы медиане
Иногда может понадобиться найти не максимально усреднённый показатель, а наиболее частый. Например, когда нужно выяснить самый популярный размер в магазине одежды. В таком случае нужно использовать моду. Это значение, которое встречается чаще других. Так, в ряде «1, 2, 1, 1, 3, 8, 10, 1, 87», мода — это 1. Модой может быть сразу несколько чисел. Как и медиану, её можно посчитать с помощью онлайн‑калькулятора и Excel.
Помимо медианы, могут использоваться процентили, квантили и квартили. Они нужны для более сложных вычислений. Например, чтобы посчитать, сколько процентов людей в стране зарабатывают 50 тысяч рублей или меньше. Показатели разделяют данные на равные части: процентили — на 100, квантили — на 10, квартили — на четыре. Так, медиана — это 50‑й процентиль или второй квартиль.
