Спортивное программирование. Занятие 2. Решение задач с применением сортировки, двоичный поиск

1.

Спортивное
программирование
Занятие 2
Решение задач с применением сортировки,
двоичный поиск
Шиян В.И.
Кубанский государственный университет
кафедра вычислительных технологий

2.

Решение задач с
применением сортировки
Бывает, что задачу легко решить за время
O(n2) с помощью полного перебора, но такой
алгоритм будет работать долго, если размер
данных велик. Вообще, при проектировании
алгоритмов часто требуется найти алгоритм
с временной сложностью O(n) или O(n log n)
для задачи, которая тривиально решается
за время O(n2). Один из способов добиться
этой цели – применить сортировку.
2

3.

Решение задач с
применением сортировки
Допустим, к примеру, что хочется проверить, все
ли элементы массива уникальны. Можно было бы
просто сравнить все пары элементов за время
O(n2):
bool ok = true;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] == arr[j]) ok = false;
}
}
3

4.

Решение задач с
применением сортировки
Однако задачу можно решить за время
O(n log n), если сначала отсортировать массив.
Тогда все равные элементы окажутся рядом,
поэтому их легко найти за время O(n):
bool ok = true;
sort(arr, arr + n);
for (int i = 0; i < n - 1; i++) {
if (arr[i] == arr[i + 1]) ok = false;
}
4

5.

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

6.

Решение задач с применением
сортировки
(алгоритм заметающей прямой)
В алгоритме заметающей прямой задача
моделируется как множество событий,
обрабатываемых в определенном порядке.
Пусть имеется ресторан, и известно время
прихода и ухода всех клиентов в течение
дня. Задача состоит в том, чтобы найти
максимальное число клиентов,
находившихся в ресторане одновременно.
6

7.

Решение задач с применением
сортировки
(алгоритм заметающей прямой)
На рисунке показан пример с четырьмя
клиентами: A, B, C и D. В данном случае
максимальное число одновременно
присутствующих клиентов равно 3: в
промежутке между приходом A и уходом B.
7

8.

Решение задач с применением
сортировки
(алгоритм заметающей прямой)
Для решения задачи будем создавать для
каждого клиента два события: приход и
уход. Затем отсортируем события по
времени и обойдем их. Чтобы найти
максимальное число клиентов, заведем
счетчик и будем увеличивать его значение,
когда клиент приходит, и уменьшать, когда
уходит. Наибольшее значение,
принимаемое счетчиком, и будет искомым
ответом.
8

9.

Решение задач с применением
сортировки
(алгоритм заметающей прямой)
На рисунке показаны события в нашем
примере. Каждому клиенту сопоставлено
два события: «+» обозначает приход, а
«–» – уход. Найденный алгоритм работает
за время O(n log n), потому что сортировка
событий занимает время O(n log n), а
заметание – время O(n).
9

10.

Решение задач с применением
сортировки
(составление расписания)
Многие задачи можно решить, отсортировав
входные данные, а затем воспользовавшись
жадной стратегией для построения
решения. Жадный алгоритм всегда делает
выбор, который кажется наилучшим в
данный момент, и впоследствии не
пересматривает принятые ранее решения.
10

11.

Решение задач с применением
сортировки
(составление расписания)
Рассмотрим следующую задачу: n событий
заданы моментами начала и конца, требуется
составить расписание, включающее как можно
больше событий. Так, на рисунке приведен
пример, когда оптимальное решение включает
два события.
11

12.

Решение задач с применением
сортировки
(составление расписания)
В этой задаче сортировать входные данные
можно несколькими способами. Первая
стратегия – отсортировать события по
продолжительности и выбирать самые
короткие события. Но, как видно из
рисунка, такая стратегия работает не
всегда.
12

13.

Решение задач с применением
сортировки
(составление расписания)
Тогда на ум приходит другая
идея – отсортировать события по времени
начала и выбирать в качестве следующего
событие, которое начинается как можно
раньше. Но и для этой стратегии можно
найти контрпример – смотри рисунок.
13

14.

Решение задач с применением
сортировки
(составление расписания)
Третья идея – отсортировать события по времени конца
и выбирать в качестве следующего событие, которое
заканчивается как можно раньше. Оказывается, что
этот алгоритм всегда дает оптимальное решение. Чтобы
доказать это, рассмотрим, что произойдет, если сначала
выбрать событие, которое заканчивается позже, чем
событие, заканчивающееся первым. Тогда число
вариантов выбора следующего события окажется никак
не больше, чем если бы была использована
предложенная стратегия. Следовательно, выбор события,
заканчивающегося позже, никогда не даст лучшего
решения, и, значит, жадный алгоритм правилен.
14

15.

Решение задач с применением
сортировки
(работы и сроки исполнения)
Наконец, предположим, что дано n работ и для каждой
указаны продолжительность и крайний срок. Наша
задача – выбрать порядок выполнения работ. Для каждой
работы нам начисляется d – x баллов, где d – крайний срок
исполнения работы, а x – момент ее фактического
завершения.
Какое максимальное число баллов можно заработать?
Предположим, что заданы такие работы:
Работа
Продолжительность
Крайний срок
A
4
2
B
3
10
C
2
8
D
4
15
15

16.

Решение задач с применением
сортировки
(работы и сроки исполнения)
На рисунке показано оптимальное
расписание работ в этом примере. При
таком расписании за C начисляется 6
баллов, за B – 5 баллов, за A
начисляется – 7 баллов, за D – 2 балла.
Итого – 6 баллов.
16

17.

Решение задач с применением
сортировки
(работы и сроки исполнения)
Оказывается, что оптимальное решение
задачи вообще не зависит от крайних
сроков, а правильная жадная стратегия
заключается в том, чтобы выполнять работы
в порядке возрастания
продолжительностей. Действительно,
если в некотором решении сначала
выполняется длинная работа, а за
ней – более короткая, то решение можно
улучшить, поменяв эти две работы местами.
17

18.

Решение задач с применением
сортировки
(работы и сроки исполнения)
На рисунке показаны две работы X и Y продолжительностью
a и b соответственно. Изначально выполнение X
запланировано раньше Y. Но, поскольку a > b, работы
следует поменять местами. Теперь за X начисляется на b
баллов меньше, а за Y – на a баллов больше, поэтому
общее число баллов увеличивается на a − b > 0. Таким
образом, в оптимальном решении короткие работы всегда
предшествуют длинным, поэтому работы следует
отсортировать по продолжительности.
18

19.

Двоичный поиск
Двоичный поиск – это алгоритм с
временной сложностью O(log n), который,
например, позволяет эффективно
проверить, встречается ли в массиве
заданное значение. Сначала рассмотрим
реализацию двоичного поиска, а затем
посмотрим, как ей воспользоваться для
нахождения оптимальных решений задач.
19

20.

Двоичный поиск
(реализация поиска)
Пусть дан отсортированный массив с n
элементами, и необходимо проверить,
встречается ли в нем значение x. Обсудим
два способа реализовать алгоритм
двоичного поиска для решения этой задачи.
20

21.

Двоичный поиск
(реализация поиска)
Первый метод. Самый распространенный способ
реализации двоичного поиска напоминает поиск
слова в словаре. Определено понятие активного
подмассива, который первоначально содержит все
элементы массива. Алгоритм состоит из ряда
шагов, на каждом из которых диапазон поиска
делится пополам. На каждом шаге проверяется
средний элемент активного подмассива. Если
средний элемент совпадает с искомым значением,
то поиск заканчивается. В противном случае поиск
рекурсивно продолжается в левой или правой
половине подмассива в зависимости от значения
среднего элемента.
21

22.

Двоичный поиск
(реализация поиска)
На рисунке показано, как в массиве ищется
элемент со значением 9.
22

23.

Двоичный поиск
(реализация поиска)
Ниже приведена реализация поиска:
int a = 0, b = n - 1;
while (a <= b) {
int k = (a + b) / 2;
if (arr[k] == x) {
// x найден в позиции с индексом k
}
if (arr[k] < x) a = k + 1;
else b = k - 1;
}
В этой реализации активный подмассив занимает позиции с индексами в
диапазоне a … b, а начальный диапазон равен 0 … n − 1. На каждом шаге
алгоритм уменьшает размер массива вдвое, так что временная сложность
составляет O(log n).
23

24.

Двоичный поиск
(реализация поиска)
Второй метод. Другой способ реализации
двоичного поиска заключается в том, чтобы
просматривать массив слева направо,
совершая прыжки. Начальная длина прыжка
равна n/2, и на каждом шаге она уменьшается
вдвое: n/4, n/8, n/16 и т. д., пока, наконец, не
станет равна 1. На каждом шаге очередной
прыжок совершается при условии, что не
произойдет выхода за пределы массива или
остановке на элементе, значение которого
превышает искомое. После всех прыжков либо
искомый элемент будет найден, либо он
заведомо не встречается в массиве.
24

25.

Двоичный поиск
(реализация поиска)
На рисунке показано применение этого
метода на конкретном примере.
25

26.

Двоичный поиск
(реализация поиска)
Ниже приведена реализация:
int k = 0;
for (int b = n / 2; b >= 1; b /= 2) {
while (k + b < n && arr[k + b] <= x) k += b;
}
if (arr[k] == x) {
// x найден в позиции с индексом k
}
Здесь переменная b содержит текущую длину прыжка.
Временная сложность алгоритма равна O(log n), потому что код
в цикле while выполняется не более двух раз для каждой длины
прыжка.
26

27.

Двоичный поиск
(нахождение оптимальных решений)
Пусть нужно решить некоторую задачу, и
существует функция valid(x), возвращающая
true, если x – допустимое решение, и false в
противном случае. Кроме того, известно, что
valid(x) равно false, когда x < k, и равно true,
когда x ≥ k. В такой ситуации можно
использовать двоичный поиск для
эффективного нахождения k.
27

28.

Двоичный поиск
(нахождение оптимальных решений)
Идея в том, чтобы с помощью двоичного поиска
найти наибольшее значение x, для которого valid(x)
равно false. Тогда следующее число
k = x + 1 – наименьшее значение, для которого
valid(k) равно true. Поиск можно реализовать
следующим образом:
int x = -1;
for (int b = z; b >= 1; b /= 2) {
while (!valid(x + b)) x += b;
}
int k = x + 1;
28

29.

Двоичный поиск
(нахождение оптимальных решений)
Начальная длина прыжка z должна быть
верхней границей ответа, т. е. любым
значением, для которого точно известно, что
valid(z) равно true. Алгоритм вызывает функцию
valid O(log z) раз, поэтому время работы
зависит от функции valid. Так, если эта функция
работает время O(n), то сложность алгоритма
равна O(n log z).
29

30.

Двоичный поиск
(нахождение оптимальных решений)
Пример. Рассмотрим следующую задачу: нам
нужно выполнить k заданий на n машинах.
Каждой машине i сопоставлено целое число
pi – время выполнения одного задания. За
какое минимальное время можно обработать
все задания?
30

31.

Двоичный поиск
(нахождение оптимальных решений)
Пусть k = 8, n = 3, а времена обработки p1 = 2,
p2 = 3, p3 = 7. В этом случае минимальное
общее время обработки равно 9, как следует из
плана, показанного на рисунке.
31

32.

Двоичный поиск
(нахождение оптимальных решений)
Пусть k = 8, n = 3, а времена обработки p1 = 2,
p2 = 3, p3 = 7. В этом случае минимальное
общее время обработки равно 9, как следует из
плана, показанного на рисунке.
32

33.

Двоичный поиск
(нахождение оптимальных решений)
Назовем valid(x) функцию, которая определяет,
можно ли обработать все задания, используя
не более x единиц времени. В нашем примере
valid(9), очевидно, равно true, что доказывается
планом на рисунке. С другой стороны, valid(8)
должно быть равно false, потому что
минимальное время обработки равно 9.
33

34.

Двоичный поиск
(нахождение оптимальных решений)
Вычислить значение valid(x) легко, потому что
каждая машина i может выполнить не более
⌊x/pi⌋ заданий за x единиц времени.
Следовательно, если сумма всех ⌊x/pi⌋ равна k
или больше, то x – допустимое решение. Далее
можно применить двоичный поиск, чтобы найти
минимальное значение x, для которого valid(x)
равно true.
34