Частичное упрядочение

выбора k-го элемента на основе процедуры разделения Partition
Линейный алгоритм

выбора k-го элемента

+ 1 ) –й по возрастанию
a < b
Линейный (полный) порядок

Tn на множестве из n = 5 элементов

a < b,
c < d < e < g,
d < f < g

Skk – медиана (n = 2k + 1)

Разделение
Wji →
(n = i + j )

список из n элементов и натуральное число k.
Требуется: найти элемент,

который в отсортированном в возрастающем порядке списке занимал бы k-ую позицию.
Более точно – получить Sn-kk-1

k –й по возрастанию

Тривиальная нижняя граница: n – 1.
При k ≤ n / log2n построить пирамиду за O(n).
Затем выбрать из неё k наименьших за время O(n + k log2n) = O(n).

элемент массива, p-й по порядку от начала массива (от 1-го

элемента)

x

≤ x

> x

p

L

R

L

p−1

p+1

R

k < p

k < p

k > p

k

k

k);
var p: Index;
begin
Partition (a, L, R, p);
if p > k

then Select (a, L, p – 1, k)
else if p < k then Select (a, p + 1, R, k)
else {p = k, ничего}
end;
Можно превратить в итеративную версию, т.к. один альтернативный рекурсивный вызов

пополам

2. «Средний» случай
Пусть размер подзадачи при рекурсивном вызове есть не

более, чем αn, где n – размер текущей задачи, а 0 < α < 1.
Тогда T(n) ≤ an + T (αn).
Покажем, что T(n) ≤ Сn, т.е. T(n) = O(n).
Действительно, T(n) ≤ an + Сαn = n (a + Сα) ≤ Сn (хотим).
(a + Сα ) ≤ С → a ≤ С − Сα = С (1 − α) → С ≥ a/(1 − α).
Например, при α = 0.9 должно быть С ≥ 10a
3. Худший случай – O (n2). → Рандомизированная выборка.

Находить гарантированно «удачный» опорный (разделяющий) элемент
2. Для этого породить много

маленьких порядков и из них извлечь нужный

Обозначим сложность алгоритма как 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). Получим состояние, изображенное на следующем рисунке

строк
4q+3
4q+3
3q
3q



A
A
B
B
C
D
C + D


4q+3
4q+3
К 3-му шагу:

из C + D относительно медианы медиан (ММ). Каждая тройка

распределяется за 2 сравнения. Всего имеем 4q действий:
4q ≤ 2(2q +1)=(2/7)n
Оценим размеры правой и левой частей относительно ММ.
A’=A+ (добавка из C + D ) B’=B+ (добавка из C + D )
Максимальный размер A’ или B’ равен
(4q + 3) + (6q) = 10q + 3
Остальные элементы (4q + 4) «отсекаются» на шаге 4.
10q + 3 ≤ 10q + 5 = 5(2q +1)=(5/7)n

или «влево» от ММ
При номер(ММ) > k → выбор из

сегмента L..ММ−1
При номер(ММ) < k → выбор из сегмента ММ+1..R
При номер(ММ) = k → Return
Стоимость шага 4 есть T ( (5/7)n )
Итак общий баланс по всем 4-м шагам:

.
Пусть T(n) ≤ Сn, тогда

сортировка,
при n > 210.

При разбиении на «пятерки» получили бы

T(n) ≤ 18n.


Общий метод
(проектная модель) разработки алгоритмов
Prune & Search или Отсечение и Поиск

ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ