O(n log n)
, поэтому от неё зависит время выполнения1, 2.def nlogn_median(l):
l = sorted(l)
if len(l) % 2 == 1:
return l[len(l) / 2]
else:
return 0.5 * (l[len(l) / 2 - 1] + l[len(l) / 2])
lesser_els
great_els
lesser_els
есть k или больше элементов, рекурсивно обходим список lesser_els
в поисках k-того элемента.lesser_els
меньше, чем k элементтов, рекурсивно обходим список greater_els
. Вместо поиска k мы ищем k-len(lesser_els)
.Возьмём представленный ниже список. Мы хотим найти медиану.
l = [9,1,0,2,3,4,6,8,7,10,5]
len(l) == 11, поэтому мы ищем шестой наименьший элемент
Сначала нам нужно выбрать опорный элемент (pivot). Мы случайным образом выбираем индекс 3.
Значение элемента с этим индексом равно 2.
Разбиваем список на группы согласно pivot:
[1,0,2], [9,3,4,6,8,7,10,5]
Нам нужен шестой элемент. 6-len(left) = 3, поэтому нам нужен
третий наименьший элемент в правом массиве
Теперь мы ищем третий наименьший элемент в следующем массиве:
[9,3,4,6,8,7,10,5]
Мы случайным образом выбираем индекс, который будет нашим pivot.
Мы выбрали индекс 2, значение в котором равно l[2]=6
Разбиваем на группы согласно pivot:
[3,4,5,6] [9,7,10]
Нам нужен третий наименьший элемент, поэтому мы знаем, что это
третий наименьший элемент в левом массиве
Теперь мы ищем третий наименьший в следующем массиве:
[3,4,5,6]
Мы случайным образом выбираем индекс, который будет нашим pivot.
Мы выбрали индекс 1, значение в котором равно l[1]=4
Разбиваем на группы согласно pivot:
[3,4] [5,6]
Нам нужен третий наименьший элемент, поэтому мы знаем, что это
наименьший элемент в правом массиве.
Теперь мы ищем наименьший элемент в следующем массиве:
[5,6]
На этом этапе у нас есть базовый вариант, выбирающий наибольший
или наименьший элемент на основании индекса.
Нам нужен наименьший элемент, то есть 5.
return 5
quickselect_median
будет вызывать quickselect
с нужными индексами.import random
def quickselect_median(l, pivot_fn=random.choice):
if len(l) % 2 == 1:
return quickselect(l, len(l) / 2, pivot_fn)
else:
return 0.5 * (quickselect(l, len(l) / 2 - 1, pivot_fn) +
quickselect(l, len(l) / 2, pivot_fn))
def quickselect(l, k, pivot_fn):
"""
Выбираем k-тый элемент в списке l (с нулевой базой)
:param l: список числовых данных
:param k: индекс
:param pivot_fn: функция выбора pivot, по умолчанию выбирает случайно
:return: k-тый элемент l
"""
if len(l) == 1:
assert k == 0
return l[0]
pivot = pivot_fn(l)
lows = [el for el in l if el < pivot]
highs = [el for el in l if el > pivot]
pivots = [el for el in l if el == pivot]
if k < len(lows):
return quickselect(lows, k, pivot_fn)
elif k < len(lows) + len(pivots):
# Нам повезло и мы угадали медиану
return pivots[0]
else:
return quickselect(highs, k - len(lows) - len(pivots), pivot_fn)
O(n)
. Давайте докажем это.O(n)
. «Среднее» в этом контексте означает, что в среднем алгоритм будет выполняться за O(n)
. С технической точки зрения, нам может очень не повезти: на каждом шаге мы можем выбирать в качестве pivot наибольший элемент. На каждом этапе мы сможем избавляться от одного элемента из списка, и в результате получим скорость O(n^2)
, а не O(n)
.O(n)
при использовании его вместе с quickselect. Этот алгоритм был разработан в 1973 году Блумом (Blum), Флойдом (Floyd), Праттом (Pratt), Ривестом (Rivest) и Тарьяном (Tarjan). Если моего объяснения вам не хватит, то можете изучить их статью 1973 года. Вместо того, чтобы описывать алгоритм, я подробно прокомментирую мою реализацию на Python:def pick_pivot(l):
"""
Выбираем хорошй pivot в списке чисел l
Этот алгоритм выполняется за время O(n).
"""
assert len(l) > 0
# Если элементов < 5, просто возвращаем медиану
if len(l) < 5:
# В этом случае мы возвращаемся к первой написанной нами функции медианы.
# Поскольку мы выполняем её только для списка из пяти или менее элементов, она не
# зависит от длины входных данных и может считаться постоянным
# временем.
return nlogn_median(l)
# Сначала разделим l на группы по 5 элементов. O(n)
chunks = chunked(l, 5)
# Для простоты мы можем отбросить все группы, которые не являются полными. O(n)
full_chunks = [chunk for chunk in chunks if len(chunk) == 5]
# Затем мы сортируем каждый фрагмент. Каждая группа имеет фиксированную длину, поэтому каждая сортировка
# занимает постоянное время. Поскольку у нас есть n/5 фрагментов, эта операция
# тоже O(n)
sorted_groups = [sorted(chunk) for chunk in full_chunks]
# Медиана каждого фрагмента имеет индекс 2
medians = [chunk[2] for chunk in sorted_groups]
# Возможно, я немного повторюсь, но я собираюсь доказать, что нахождение
# медианы списка можно произвести за доказуемое O(n).
# Мы находим медиану списка длиной n/5, поэтому эта операция также O(n)
# Мы передаём нашу текущую функцию pick_pivot в качестве создателя pivot алгоритму
# quickselect. O(n)
median_of_medians = quickselect_median(medians, pick_pivot)
return median_of_medians
def chunked(l, chunk_size):
"""Разделяем список `l` на фрагменты размером `chunk_size`."""
return [l[i:i + chunk_size] for i in range(0, len(l), chunk_size)]
3/5*1/2=3/10
. Поэтому на каждом этапе мы избавляемся по крайней мере от 30% строк.T(n)
:O(n)
. Быстрое решение заключается в том, чтобы положиться на основную теорему о рекуррентных соотношениях. Мы попадаем в третий случай теоремы, при котором работа на каждом уровне доминирует над работой подзадач. В этом случае общая работа будет просто равна работе на каждом уровне, то есть O(n)
.O(n)
для выбора опорного элемента (который достаточно хорош для quickselect). Соединив их, мы получили алгоритм нахождения медианы (или n-ного элемента в списка) за линейное время!C++
используется алгоритм под названием introselect, в котором применено сочетание heapselect и quickselect; предел его выполнения O(n log n)
. Introselect позволяет использовать обычно быстрый алгоритм с плохим верхним пределом в сочетании с алгоритмом, который медленнее на практике, но имеет хороший верхний предел. Реализации начинают с быстрого алгоритма, но возвращаются к более медленному, если не могут выбрать эффективные опорные элементы.К сожалению, не доступен сервер mySQL