a < b,
c < d < e < g,
d < f < g
Skk – медиана (n = 2k + 1)
Разделение
Wji →
(n = i + j )
k –й по возрастанию
Тривиальная нижняя граница: n – 1.
При k ≤ n / log2n построить пирамиду за O(n).
Затем выбрать из неё k наименьших за время O(n + k log2n) = O(n).
x
≤ x
> x
p
L
R
L
p−1
p+1
R
k < p
k < p
k > p
k
k
Обозначим сложность алгоритма как T(n).
Пусть n = 7(2q + 1). (Если нет, то добавим не более 13 элементов +∞)
Шаг 1. Сортируем семерки (каждую из 2q + 1 штук) за 13(2q + 1) шагов.
13(2q + 1) = (13/7) 7(2q + 1) = (13/7)n.
В каждой семерке знаем медиану.
Шаг 2. Рекурсивно этим же алгоритмом находим медиану медиан «семерок» за время T(n/7). Получим состояние, изображенное на следующем рисунке
Если не удалось найти и скачать доклад-презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:
Email: Нажмите что бы посмотреть