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

Сентябрь 3, 2022

Главная
Алгебра
Частичное упрядочение

Содержание

2. 26.03.2007 Частичное упорядочение Частичный порядок * Выбор ← Sji (n=i+j+1) ( i + 1 ) –й
3. 26.03.2007 Частичное упорядочение Выбор k-го элемента Синонимы: порядковые статистики, ранги, ранговые статистики Даны: список из n
4. 26.03.2007 Частичное упорядочение Выбор k-го элемента Алгоритм на основе процедуры Partition x – элемент массива, p-й
5. 26.03.2007 Частичное упорядочение Алгоритм на основе процедуры Partition Proc Select (a, L, R, k); var p:
6. 26.03.2007 Частичное упорядочение Алгоритм на основе процедуры Partition Анализ алгоритма Благоприятный случай – деление пополам 2.
7. 26.03.2007 Частичное упорядочение Линейный алгоритм выбора k-го элемента (В худшем случае) Идея: 1. Находить гарантированно «удачный»
8. 26.03.2007 Частичное упорядочение Линейный алгоритм выбора k-го элемента Состояние после 2-го шага q строк q строк
9. 26.03.2007 Частичное упорядочение Линейный алгоритм выбора k-го элемента Шаг 3. «Разбрасываем» 6q элементов из C +
10. 26.03.2007 Частичное упорядочение Линейный алгоритм выбора k-го элемента Шаг 4. Рекурсивный вызов «вправо» или «влево» от
11. 26.03.2007 Частичное упорядочение Линейный алгоритм выбора k-го элемента Покажем, что T(n) = O(n) . Пусть T(n)
12. 26.03.2007 Частичное упорядочение Линейный алгоритм выбора k-го элемента Этот алгоритм лучше, чем прямая сортировка, при n
13. 26.03.2007 Частичное упорядочение Метод Prune & Search или Отсечение и Поиск
14. 26.03.2007 Частичное упорядочение Метод Prune & Search или Отсечение и Поиск
15. 26.03.2007 Частичное упорядочение Объява про текущий контроль по разделу «Сортировка»
17. Скачать презентацию

Слайд 2

26.03.2007
Частичное упорядочение
Частичный порядок
*
Выбор
← Sji
(n=i+j+1)
( i + 1 ) –й

по возрастанию

a < b

Линейный (полный) порядок Tn на множестве из n = 5 элементов

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

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

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

Слайд 3

26.03.2007
Частичное упорядочение
Выбор k-го элемента
Синонимы: порядковые статистики, ранги, ранговые статистики
Даны: список

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

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

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

Слайд 4

26.03.2007
Частичное упорядочение
Выбор k-го элемента
Алгоритм на основе процедуры Partition
x – элемент

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

≤ x

> x

p−1

p+1

k < p

k > p

Слайд 5

26.03.2007
Частичное упорядочение
Алгоритм на основе процедуры Partition
Proc Select (a, L, R, 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;
Можно превратить в итеративную версию, т.к. один альтернативный рекурсивный вызов

Слайд 6

26.03.2007
Частичное упорядочение
Алгоритм на основе процедуры Partition
Анализ алгоритма
Благоприятный случай – деление пополам
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). → Рандомизированная выборка.

Слайд 7

26.03.2007
Частичное упорядочение
Линейный алгоритм выбора k-го элемента
(В худшем случае)
Идея: 1. Находить гарантированно

«удачный» опорный (разделяющий) элемент
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). Получим состояние, изображенное на следующем рисунке

Слайд 8

26.03.2007
Частичное упорядочение
Линейный алгоритм выбора k-го элемента Состояние после 2-го шага
q строк
q строк
4q+3
4q+3
3q
3q
A
A
B
B
C
D
C

+ D

4q+3

К 3-му шагу:

Слайд 9

26.03.2007
Частичное упорядочение
Линейный алгоритм выбора k-го элемента
Шаг 3. «Разбрасываем» 6q элементов из

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

Слайд 10

26.03.2007
Частичное упорядочение
Линейный алгоритм выбора k-го элемента
Шаг 4. Рекурсивный вызов «вправо» или

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

Слайд 11

26.03.2007
Частичное упорядочение
Линейный алгоритм выбора k-го элемента
Покажем, что T(n) = O(n) .
Пусть

T(n) ≤ Сn, тогда

Слайд 12

26.03.2007
Частичное упорядочение
Линейный алгоритм выбора k-го элемента
Этот алгоритм лучше, чем прямая сортировка,

при n > 210.
При разбиении на «пятерки» получили бы T(n) ≤ 18n.
Общий метод
(проектная модель) разработки алгоритмов
Prune & Search или Отсечение и Поиск

Слайд 13

26.03.2007
Частичное упорядочение
Метод Prune & Search или Отсечение и Поиск

Слайд 14

26.03.2007
Частичное упорядочение
Метод Prune & Search или Отсечение и Поиск

Слайд 15

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

Содержание

26.03.2007Частичное упорядочениеЧастичный порядок*Выбор← Sji (n=i+j+1)( i + 1 ) –й

26.03.2007Частичное упорядочениеВыбор k-го элемента Синонимы: порядковые статистики, ранги, ранговые статистикиДаны: список

26.03.2007Частичное упорядочениеВыбор k-го элемента Алгоритм на основе процедуры Partitionx – элемент

26.03.2007Частичное упорядочениеАлгоритм на основе процедуры PartitionProc Select (a, L, R, k);var

26.03.2007Частичное упорядочениеАлгоритм на основе процедуры PartitionАнализ алгоритмаБлагоприятный случай – деление пополам2.

26.03.2007Частичное упорядочениеЛинейный алгоритм выбора k-го элемента(В худшем случае)Идея: 1. Находить гарантированно

26.03.2007Частичное упорядочениеЛинейный алгоритм выбора k-го элемента Состояние после 2-го шагаq строкq строк4q+34q+33q3qAABBCDC

26.03.2007Частичное упорядочениеЛинейный алгоритм выбора k-го элементаШаг 3. «Разбрасываем» 6q элементов из

26.03.2007Частичное упорядочениеЛинейный алгоритм выбора k-го элементаШаг 4. Рекурсивный вызов «вправо» или

26.03.2007Частичное упорядочениеЛинейный алгоритм выбора k-го элементаПокажем, что T(n) = O(n) .Пусть

26.03.2007Частичное упорядочениеЛинейный алгоритм выбора k-го элементаЭтот алгоритм лучше, чем прямая сортировка,

26.03.2007Частичное упорядочениеМетод Prune & Search или Отсечение и Поиск

26.03.2007Частичное упорядочениеМетод Prune & Search или Отсечение и Поиск

26.03.2007Частичное упорядочениеОбъява про текущий контроль по разделу «Сортировка»

Похожие презентации

26.03.2007
Частичное упорядочение
Частичный порядок
*
Выбор
← Sji
(n=i+j+1)
( i + 1 ) –й

26.03.2007
Частичное упорядочение
Выбор k-го элемента
Синонимы: порядковые статистики, ранги, ранговые статистики
Даны: список

26.03.2007
Частичное упорядочение
Выбор k-го элемента
Алгоритм на основе процедуры Partition
x – элемент

26.03.2007
Частичное упорядочение
Алгоритм на основе процедуры Partition
Proc Select (a, L, R, k);
var

26.03.2007
Частичное упорядочение
Алгоритм на основе процедуры Partition
Анализ алгоритма
Благоприятный случай – деление пополам
2.

26.03.2007
Частичное упорядочение
Линейный алгоритм выбора k-го элемента
(В худшем случае)
Идея: 1. Находить гарантированно

26.03.2007
Частичное упорядочение
Линейный алгоритм выбора k-го элемента Состояние после 2-го шага
q строк
q строк
4q+3
4q+3
3q
3q
A
A
B
B
C
D
C

26.03.2007
Частичное упорядочение
Линейный алгоритм выбора k-го элемента
Шаг 3. «Разбрасываем» 6q элементов из

26.03.2007
Частичное упорядочение
Линейный алгоритм выбора k-го элемента
Шаг 4. Рекурсивный вызов «вправо» или

26.03.2007
Частичное упорядочение
Линейный алгоритм выбора k-го элемента
Покажем, что T(n) = O(n) .
Пусть

26.03.2007
Частичное упорядочение
Линейный алгоритм выбора k-го элемента
Этот алгоритм лучше, чем прямая сортировка,

26.03.2007
Частичное упорядочение
Метод Prune & Search или Отсечение и Поиск

26.03.2007
Частичное упорядочение
Метод Prune & Search или Отсечение и Поиск

26.03.2007
Частичное упорядочение
Объява
про текущий контроль
по разделу «Сортировка»