Алгоритм поиска медианы в медиане медиан

Question

Алгоритм поиска медианы в медиане медиан

Я знаю, что формула для алгоритма медианы медиан:T(n)<= T(0.7n)+T(0.2n)+O(n) а также O(n) пришел от нахождения медианы каждого блока (размер 5), и мне интересно, почему требуется O(n), чтобы найти медиану каждого блока.. это звучит как поиск медианы одного блока занимает O(1), Как это возможно?

-1

algorithm sorting median median-of-medians

Источник

user8093947 15 окт '18 в 09:57

1 ответ

Решение

Другие вопросы по тегам algorithm sorting median median-of-medians

user3768871 15 окт '18 в 10:03 2018-10-15 10:03 · Accepted Answer · 2018-10-15 10:03

Размер каждого блока постоянен (5). Следовательно, поиск медианы каждого блока находится в O(1) (отсортировать блок в O(1) и возьмите средний индекс в качестве медианы). Поэтому нахождение медианы всех блоков находится в O(n), И после этого найдите медиану медианы каждого блока, на которую есть ответ в другом вашем вопросе.