Как найти середину медианы чисел

Формула медианы числового набора, пример вычисления медианы числового ряда: 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

Понятие медианы чисел широко используется в математической статистике. И хотя вычисление медианы не составляет большой сложности, мы сделали калькулятор, который поможет рассчитать медианное значение ряда чисел онлайн с подробным решением. Причем количество чисел не важно, он рассчитает медиану 3, 4, 5 чисел так же быстро, как и для 1000 чисел.

Калькулятор медиана чисел

Как найти медиану чисел

Лучше рассмотреть процесс вычисления медианы на примере. Пусть у нас есть ряд чисел: 13 19 24 17 15 11. Для удобства числа будет записывать через пробел. Найдем его медиану. Для начала необходимо расположить числа в порядке возрастания. Эта процедура называется сортировкой. Получим новый ряд: 11 13 15 17 19 24. Так как количество чисел в ряду равно 6, а число 6 четное, то середина ряда будет между числами 15 и 17. Найдем среднее этих двух чисел: (15 + 17) / 2 = 16. Это и будет медианой ряда. Не стоит путать медиану, среднее гармоническое и среднее арифметическое — это принципиально разные понятия.

Рассмотрим другой пример, когда количество чисел в ряду нечетное. Есть такой ряд: 18 46 10 5 38. Найдем медиану набора этих чисел. Отсортируем ряд по возрастанию и получим ряд: 5 10 18 38 48. Так как количество чисел в этом ряду 5, то у него есть середина — это элемент с номером 2. Значит медиана этого ряда равна элементу с номером 2. Получаем ответ 18.

И еще пример — найдем медиану чисел 158 166 134 130 132. Отсортируем и получим ряд 130 132 134 158 166. Количество чисел нечетное и равно 5, значит средний элемент имеет номер 3. Третий элемент нашего отсортированного ряда — число 134. Это и есть медиана.

Медиана ряда чисел Автор admin средний рейтинг 3/5 — 261 рейтинги пользователей

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

Медиана — это число, стоящее посередине упорядоченного по возрастанию ряда чисел (в случае, если количество чисел нечетное), или же полусумма двух стоящих в середине чисел (если количество чисел в ряду четное).

На письме медиану обозначают как $Me$.

Стоит отметить, что медиана и среднее арифметическое — это не одно и то же. В первом случае мы будем брать число из середины ряда, а во втором — среднее значение.

Рассмотрим на примере. Нам дан определенный числовой ряд, состоящий из $13$ значений:

$$-3, 0, 0, 0, 3, 4, textcolor{blue}{8}, 8, 8, 8, 12, 15, 100$$

В данном ряду все числа расставлены по возрастанию, поэтому из $13$ позиций нам нужно найти ту, которая будет стоять в центре ряда. Ей станет позиция под номером $7$. Если мы посмотрим на числовой ряд, то можем увидеть, что на седьмом месте стоит число $textcolor{blue}{8}$. Таким образом, мы нашли медиану данного числового ряда, а в ответе можем записать, что $Me=8$.

Алгоритм нахождения медианы

Искать медиану в числовом ряде достаточно просто, для этого достаточно всего лишь придерживаться определенного алгоритма:

1. Первым шагом будет нужно упорядочить числовой набор, выписав все числа последовательно в порядке возрастания.
2. Затем, чтобы было удобнее находить медиану, следует поочередно зачеркивать одновременно самое большое и самое маленькое числа, то есть одно значение из начала числового ряда, а другое — из его конца. Это нужно делать до тех пор, пока в середине не останется одно (если ряд имеет нечетное количество чисел) или два (если ряд имеет четного количества чисел) значения.
3. При условии, что в центре остается одно число, его и считают медианой, поэтому в таком случае задача уже будет решена.
4. Если же в середине осталось два числа, то нужно найти их полусумму. Полученное значение и будет являться медианой числового ряда.

Попробуем применить данный алгоритм на примере. У нас имеется следующий ряд чисел:

$$19, 7, 21, 2, 15, 5$$

Прежде всего запишем все числа в порядке возрастания друг за другом:

$$2, 5, 7, 15, 19, 21$$

Теперь начнем убирать самое большое и самое маленькое значения. Сначала зачеркиваем числа $21$ и $2$, затем $19$ и $5$. Мы видим, что в середине осталось два числа, так как числовой ряд состоял из четного количества чисел.

$$textcolor{red}{2}, textcolor{red}{5}, 7, 15, textcolor{red}{19}, textcolor{red}{21}$$

Чтобы найти медиану, нам нужно сложить числа $7$ и $15$, после чего разделить их на два. Получается такой пример:

$$frac{7+15}{2}=frac{22}{2}=11$$

Значение $11$ и будет являться искомой медианой, поэтому в ответе мы можем записать, что $Me=11$.

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

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

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

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

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

Начнём с базовых понятий. Медианой называется число, стоящее в упорядоченном ряде чисел посередине. Например в ряду: 1, 2, 3, 7, 9 — тройка является медианой. Если количество чисел чётное, то за медиану принимают среднее двух стоящих в центре чисел.

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

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

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

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

medians = []
items_read = []
with open('./Median.txt', 'r') as f:
    for line in f:
        num = int(line.strip())
        for idx in range(len(items_read)):
            if num < items_read[idx]:
                items_read.insert(idx, num)
                break
        if len(items_read) % 2 == 0:
            median_pos = len(items_read) // 2
        else:
            median_pos = len(items_read) + 1 // 2
        medians.append(median_pos)

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

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

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

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

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

Пример кучи (источник)

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

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

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

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

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

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

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

class Heap(object):
    def __init__(self, array, type):
        super(Heap, self).__init__()
        self.type = type
        self.data = []
        self.heapify(array)
    
    def heapify(self, array):
        for item in array:
            self.insert(item)

    def bubble_down(self, array, index=0):
        left = 2 * index + 1 
        right = 2 * index + 2
        size = len(array)
        least = index
        if self.type == 'min':
            if left < size and array[left] < array[least]:
                least = left
            if right < size and array[right] < array[least]:
                least = right
            if least != index:
                tmp_val = array[least]
                array[least] = array[index]
                array[index] = tmp_val
                self.bubble_down(array, index=least)
        else:
            if left < size and array[left] > array[least]:
                least = left
            if  right < size and array[right] > array[least]:
                least = right
            if least != index:
                tmp_val = array[least]
                array[least] = array[index]
                array[index] = tmp_val
                self.bubble_down(array, index=least)
    
    def bubble_up(self, array, index):
        parent = (index - 1) // 2
        if self.type == 'min':
            if array[index] < array[parent] and parent >= 0:
                tmp_val = array[parent]
                array[parent] = array[index]
                array[index] = tmp_val
                self.bubble_up(array, index=parent)
        else:
            if array[index] > array[parent] and parent >= 0:
                tmp_val = array[parent]
                array[parent] = array[index]
                array[index] = tmp_val
                self.bubble_up(array, index=parent)

    def extract(self):
        root = self.data.pop(0)
        self.data.insert(0, self.data.pop(-1))
        self.bubble_down(self.data, 0)
        return root

    def insert(self, element):
        self.data.append(element)
        self.bubble_up(self.data, index=len(self.data)-1)

if __name__ == "__main__":
    a = [3,99,4,88,0,5,1,2]
    b = Heap(a, type='max')
    print(b.data)

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

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

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

Код:

from heap import Heap


top_nums = Heap([], 'min')
bot_nums = Heap([], 'max')
medians = []
with open('./Median.txt', 'r') as f:
    for line in f:
        num = int(line.strip())
        if len(top_nums.data):
            top_smallest = top_nums.data[0]
            if num > top_smallest:
                top_nums.insert(num)
            else:
                bot_nums.insert(num)
        else:
            bot_nums.insert(num)
        while len(top_nums.data) > len(bot_nums.data):
            bot_nums.insert(top_nums.extract())
        while len(top_nums.data) + 1 < len(bot_nums.data):
            top_nums.insert(bot_nums.extract())
        medians.append(bot_nums.data[0])

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

Заключение

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

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

• ЗАПИСАТЬСЯ НА ИНТЕНСИВ. ДЕНЬ 1
• ЗАПИСАТЬСЯ НА ИНТЕНСИВ. ДЕНЬ 2