Python-реализация алгоритма «медиана медиан»
Я написал эту реализацию алгоритма медианы медиан в Python, но он, похоже, не дает правильного результата, и он также не кажется мне линейной сложностью, есть идеи, где я ушел с пути?
def select(L):
if len(L) < 10:
L.sort()
return L[int(len(L)/2)]
S = []
lIndex = 0
while lIndex+5 < len(L)-1:
S.append(L[lIndex:lIndex+5])
lIndex += 5
S.append(L[lIndex:])
Meds = []
for subList in S:
print(subList)
Meds.append(select(subList))
L2 = select(Meds)
L1 = L3 = []
for i in L:
if i < L2:
L1.append(i)
if i > L2:
L3.append(i)
if len(L) < len(L1):
return select(L1)
elif len(L) > len(L1) + 1:
return select(L3)
else:
return L2
Функция называется так:
L = list(range(100))
shuffle(L)
print(select(L))
Л.Э .: Извините. GetMed была функцией, которая просто сортировала список и возвращала элемент в len (list), он должен был быть выбран там, я исправил это сейчас, но все же я получаю неправильные результаты. Что касается отступа, код работает без ошибок, и я не вижу в этом ничего плохого: - ??
LE2: Я ожидаю 50 (для текущего L), это дает мне выходы от 30 до 70, не больше, не меньше (пока)
LE3: Большое спасибо, это помогло, теперь это работает. Я путаюсь, хотя, я пытаюсь провести сравнение между этим методом и наивным, где я просто сортирую массив и выводю результаты. Теперь, из того, что я прочитал, временная сложность метода select должна быть O (n)Детерминированный отбор, Хотя я, вероятно, не могу конкурировать с разработчиками Python для оптимизации, я ожидал более близких результатов, чем получил, например, если я изменю диапазон списка на 10000000, select выводит результат за 84.10837116255952 секунд, а метод сортировки и возврата делает это в 18.92556029528825. Какие есть хорошие способы сделать этот алгоритм быстрее?