анти. Guide to Competitive
 Скачать 2.39 Mb.
|
|
Глава 4 Сортировка и поиск Многие эффективные алгоритмы основаны на сортировке входных дан- ных, поскольку благодаря сортировке задачу часто можно решить про- ще. В этой главе обсуждаются теория и практика сортировки как средства проек тирования алгоритмов. В разделе 4.1 рассматриваются три важных алгоритма сортировки: пу- зырьковая, слиянием и подсчетом. Затем мы научимся использовать алго- ритм сортировки, включенный в стандартную библиотеку C++. В разделе 4.2 показано, как создавать эффективные алгоритмы, исполь- зуя сортировку в качестве подпрограммы. Например, чтобы быстро опре- делить, являются ли все элементы массива уникальными, можно сначала отсортировать массив, а затем просто проверить пары соседних элемен- тов. В разделе 4.3 представлен алгоритм двоичного поиска – еще один важ- ный элемент построения эффективных алгоритмов. 4.1. Алгоритмы сортировки Основная задача сортировки формулируется следующим образом: дан массив, содержащий n элементов, требуется расположить элементы в по- рядке возрастания. Так, на рис. 4.1 изображен массив до и после сортиров- ки. Исходный массив Отсортированный массив Рис. 4.1. Массив до и после сортировки В этом разделе мы разберем некоторые общеизвестные алгоритмы сор- тировки и изучим их свойства. Легко спроектировать алгоритм сортиров- ки с временной сложностью O(n 2 ), но существуют и более эффективные ал- горитмы. Обсудив теорию сортировки, мы перейдем к ее практическому использованию в программах на C++. 60 Глава 4. Сортировка и поиск 4.1.1. Пузырьковая сортировка Пузырьковая сортировка – простой алгоритм с временной сложностью O(n 2 ). Он состоит из n раундов, на каждом из которых обходятся элементы массива. Если два соседних элемента расположены не в том порядке, то они переставляются. Реализовать алгоритм можно следующим образом: for (int i = 0; i < n; i++) { for (int j = 0; j < n-1; j++) { if (array[j] > array[j+1]) { swap(array[j],array[j+1]); } } } После первого раунда самый большой элемент окажется в правильной позиции. Вообще, после k раундов в правильных позициях будут нахо- диться k самых больших элементов. Следовательно, после n раундов весь массив будет отсортирован. На рис. 4.2 показан первый раунд пузырьковой сортировки массива. Рис. 4.2. Первый раунд пузырьковой сортировки Пузырьковая сортировка – пример алгоритма сортировки, в котором переставляются только соседние элементы массива. Временная сложность такого алгоритма обязательно не лучше O(n 2 ), потому что в худшем случае потребуется выполнить O(n 2 )перестановок. 4.1. Алгоритмы сортировки 61 Инверсии. Для анализа алгоритмов сортировки полезно понятие ин- версии. Так называется пара индексов массива (a, b) – такая, что a < b и array [a ] >array [ b], т. е. элементы массива расположены не в том порядке, в каком нужно. На рис. 4.3 имеется три инверсии: (3, 4), (3, 5) и (6, 7). Рис. 4.3. В этом массиве три инверсии: (3, 4), (3, 5) и (6, 7) От количества инверсий зависит объем работы, которую нужно проде- лать для сортировки массива. Массив полностью отсортирован, когда в нем нет инверсий. С другой стороны, если элементы массива расположены в обратном порядке, то число инверсий максимально и равно 2 ( 1) 1 2 ... ( 1) ( ), 2 n n n O n − + + + − = = Перестановка пары соседних элементов, расположенных не по поряд- ку, устраняет ровно одну инверсию. Поэтому если алгоритму разрешается переставлять только соседние элементы, то его временная сложность не может быть лучше O(n 2 ). 4.1.2. Сортировка слиянием Чтобы создать эффективный алгоритм сортировки, требуется пере- упорядочивать элементы, находящиеся в разных частях массива. Сущест- вует несколько таких алгоритмов, работающих за время O(n log n). Один из них – сортировка слиянием – основан на рекурсии. Этот алгоритм сорти- рует подмассив array [ a … b] следующим образом: 1. Если a = b, не делать ничего, поскольку подмассив, содержащий всего один элемент, уже отсортирован. 2. Вычислить позицию среднего элемента: k = ⌊(a + b)/2⌋. 3. Рекурсивно отсортировать подмассив array [ a … k]. 4. Рекурсивно отсортировать подмассив array [ k + 1 … b]. 5. Слить отсортированные подмассивы array [ a … k] и array [ k + 1 … b] в отсортированный подмассив array [ a … b]. На рис. 4.4 показано, как сортировка слиянием применяется к массиву из восьми элементов. Сначала массив разбивается на два подмассива из четырех элементов. Затем каждый массив сортируется рекурсивно. И на- конец, отсортированные подмассивы сливаются, образуя отсортирован- ный массив из восьми элементов. Сортировка слиянием – эффективный алгоритм, поскольку на каждом шаге размер подмассива уменьшается вдвое. А для слияния уже отсорти- 62 Глава 4. Сортировка и поиск рованных подмассивов достаточно линейного времени. Так как уровней рекурсии O(log n), а обработка на каждом уровне занимает время O(n), то временная сложность алгоритма равна O(n log n). Рис. 4.4. Сортировка массива слиянием 4.1.3. Нижняя граница временной сложности сортировки Можно ли отсортировать массив быстрее, чем за время O(n log n)? Ока- зывается, что нет, если ограничиться алгоритмами, основанными на срав- нении элементов. Чтобы доказать нижнюю границу временной сложности, будем рассмат- ривать сортировку как процесс, в котором сравнение двух элементов дает дополнительную информацию о массиве. На рис. 4.5 показано дерево, соз- даваемое в ходе этого процесса. Рис. 4.5. Ход выполнения алгоритма сортировки – сравнение элементов массива Здесь «x < y?» означает, что сравниваются элементы x и y. Если x < y, то выбирается левая ветвь дерева, иначе – правая. Результатом процесса яв- ляется множество всех возможных способов расположить элементы мас- сива, всего их n!. Поэтому высота дерева должна быть не меньше log 2 (n!)= log 2 (1)+ log 2 (2) + … + log 2 (n). 4.1. Алгоритмы сортировки 63 Чтобы получить нижнюю оценку этой суммы, оставим только последние n/ 2 элементов и заменим каждый из них на log 2 (n/2). Это дает оценку log 2 (n!) ≥ (n/2) · log 2 (n/2), так что высота дерева и число шагов алгоритма в худшем случае равны Ω(n log n). 4.1.4. Сортировка подсчетом Нижняя граница Ω(n log n)неприменима к алгоритмам, которые не сравнивают элементы массива, а используют какую-то другую информа- цию. Примером такого алгоритма является сортировка подсчетом, при которой массив сортируется за время O(n)в предположении, что все его элементы – целые числа от 0 до c и c = O(n). Мы будем использовать вспомогательный массив, индексы которого со- ответствуют элементам исходного массива. Алгоритм обходит исходный массив и вычисляет, сколько раз в нем встречается каждый элемент. На рис. 4.6 показаны исходный массив и соответствующий ему вспомогатель- ный массив. Например, в позиции 3 находится значение 2, поскольку зна- чение 3 встречается в исходном массиве 2 раза. Рис. 4.6. Сортировка массива подсчетом Построение вспомогательного массива занимает время O(n). После это- го создать отсортированный массив можно за время O(n), поскольку из вспомогательного массива можно узнать, сколько раз встречается каждый элемент. Таким образом, полная временная сложность сортировки под- счетом равна O(n). Сортировка подсчетом – очень эффективный алгоритм, но применим он, только если константа c достаточно мала, так что элементы исходного массива можно использовать в качестве индексов вспомогательного мас- сива. 4.1.5. Сортировка на практике На практике почти никогда не стоит заниматься реализацией доморо- щенного алгоритма сортировки, поскольку в стандартных библиотеках всех современных языков программирования уже имеются отличные реа- 64 Глава 4. Сортировка и поиск лизации. Причин выбрать библиотечную функцию много: она наверняка правильна, эффективна, да к тому же ее легко использовать. В C++ функция sort эффективно 1 сортирует содержимое структуры дан- ных. Например, в следующем фрагменте элементы вектора сортируются в порядке возрастания: vector<int> v = {4,2,5,3,5,8,3}; sort(v.begin(),v.end()); После сортировки вектор будет иметь вид [2, 3, 3, 4, 5, 5, 8]. По умолча- нию сортировка производится в порядке возрастания, но можно отсорти- ровать и в порядке убывания: sort(v.rbegin(),v.rend()); Обычный массив можно отсортировать следующим образом: int n = 7; // размер массива int a[] = {4,2,5,3,5,8,3}; sort(a,a+n); А ниже показано, как отсортировать строку s : string s = "monkey"; sort(s.begin(), s.end()); Под сортировкой строки понимается расположение ее символов в ал- фавитном порядке. Например, строка «monkey» превращается в «ekmnoy». Операторы сравнения. Чтобы функция sort работала, для типа сорти- руемых данных должен быть определен оператор сравнения. Во время сор- тировки он будет использоваться, когда требуется определить, какой из двух элементов больше. В большинстве типов данных C++ имеются встроенные операторы срав- нения, так что элементы таких типов будут сортироваться автоматически. Числа сортируются по значениям, строки – в лексикографическом поряд- ке. Пары сортируются сначала по первым элементам, а если они равны, то по вторым: vector int,int>> v; v.push_back({1,5}); v.push_back({2,3}); v.push_back({1,2}); sort(v.begin(), v.end()); // результат: [(1,2),(1,5),(2,3)] 1 Стандарт C++11 требует, чтобы функция sort работала за время O(n log n), фактическая реализация зависит от компилятора. 4.1. Алгоритмы сортировки 65 Точно так же кортежи сортируются сначала по первым элементам, в слу- чае их совпадения – по вторым и т. д. 2 : vector v.push_back({2,1,4}); v.push_back({1,5,3}); v.push_back({2,1,3}); sort(v.begin(), v.end()); // результат: [(1,5,3),(2,1,3),(2,1,4)] В определенных пользователем классах оператор сравнения автомати- чески не появляется. Его следует определить в виде функции operator< , которая принимает в качестве параметра другой элемент того же типа. Оператор должен возвращать true , если объект, от имени которого он вы- зывается, меньше параметра, и false в противном случае. Например, показанная ниже структура point содержит координаты точ- ки x и y . Оператор сравнения определен так, что точки сортируются снача- ла по координате x , а в случае совпадения – по координате y struct point { int x, y; bool operator<(const point &p) { if (x == p.x) return y < p.y; else return x < p.x; } }; Функции сравнения. Можно также определить внешнюю функцию сравнения и передать ее функции sort как функцию обратного вызова. На- пример, следующая функция сравнивает строки сначала по длине, а при совпадении – в лексикографическом порядке: bool comp(string a, string b) { if (a.size() == b.size()) return a < b; else return a.size() < b.size(); } Теперь вектор строк можно отсортировать следующим образом: sort(v.begin(), v.end(), comp); 2 Отметим, что в некоторых старых компиляторах для создания кортежа нужно было использовать функцию make_tuple, а не просто фигурные скобки (например, make_tuple(2,1,4) вместо {2,1,4} ). 66 Глава 4. Сортировка и поиск 4.2. Решение задач с применением сортировки Бывает, что задачу легко решить за время O(n 2 ) с помощью полного пере- бора, но такой алгоритм будет работать долго, если размер данных велик. Вообще, при проектировании алгоритмов часто требуется найти алгоритм с временной сложностью O(n)или O(n log n) для задачи, которая тривиаль- но решается за время O(n 2 ). Один из способов добиться этой цели – при- менить сортировку. Допустим, к примеру, что мы хотим проверить, все ли элементы массива уникальны. Можно было бы просто сравнить все пары элементов за время O(n 2 ): bool ok = true; for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) { if (array[i] == array[j]) ok = false; } } Однако задачу можно решить за время O(n log n), если сначала отсорти- ровать массив. Тогда все равные элементы окажутся рядом, поэтому их легко найти за время O(n): bool ok = true; sort(array, array+n); for (int i = 0; i < n-1; i++) { if (array[i] == array[i+1]) ok = false; } Есть еще несколько похожих задач, которые тоже решаются за время O(n log n), например подсчет числа различных элементов, нахождение са- мого часто встречающегося элемента и нахождение двух элементов с ми- нимальной разностью. 4.2.1. Алгоритмы заметающей прямой В алгоритме заметающей прямой задача моделируется как множество событий, обрабатываемых в определенном порядке. Пусть имеется ресто- ран, и мы знаем время прихода и ухода всех клиентов в течение дня. За- дача состоит в том, чтобы найти максимальное число клиентов, находив- шихся в ресторане одновременно. На рис. 4.7 показан пример с четырьмя клиентами: A, B, C и D. В данном случае максимальное число одновременно присутствующих клиентов равно 3: в промежутке между приходом A и уходом B. 4.2. Решение задач с применением сортировки 67 Рис. 4.7. Пример задачи о ресторане Для решения задачи будем создавать для каждого клиента два события: приход и уход. Затем отсортируем события по времени и обойдем их. Что- бы найти максимальное число клиентов, заведем счетчик и будем увели- чивать его значение, когда клиент приходит, и уменьшать, когда уходит. Наибольшее значение, принимаемое счетчиком, и будет искомым ответом. На рис. 4.8 показаны события в нашем примере. Каждому клиенту со- поставлено два события: «+» обозначает приход, а «–» – уход. Найденный алгоритм работает за время O(n log n), потому что сортировка событий занимает время O(n log n), а заметание – время O(n). Рис. 4.8. Решение задачи о ресторане с применением алгоритма заметающей прямой 4.2.2. Составление расписания Многие задачи можно решить, отсортировав входные данные, а затем воспользовавшись жадной стратегией для построения решения. Жадный алгоритм всегда делает выбор, который кажется наилучшим в данный мо- мент, и впоследствии не пересматривает принятые ранее решения. Рассмотрим следующую задачу: n событий заданы моментами начала и конца, требуется составить расписание, включающее как можно больше событий. Так, на рис. 4.9 приведен пример, когда оптимальное решение включает два события. Рис. 4.9. Пример задачи о планировании и оптимальное решение с двумя событиями В этой задаче сортировать входные данные можно несколькими спосо- бами. Первая стратегия – отсортировать события по продолжительности и выбирать самые короткие события. Но, как видно по рис. 4.10, такая стра- 68 Глава 4. Сортировка и поиск тегия работает не всегда. Тогда на ум приходит другая идея – отсортиро- вать события по времени начала и выбирать в качестве следующего собы- тие, которое начинается как можно раньше. Но и для этой стратегии можно найти контрпример – см. рис. 4.11. Рис. 4.10. Выбирая короткое событие, мы сможем выбрать только одно событие, хотя можно было бы выбрать оба длинных события Рис. 4.11. Выбирая первое событие, мы не сможем выбрать другие, хотя можно было бы выбрать два других события Третья идея – отсортировать события по времени конца и выбирать в качестве следующего событие, которое заканчивается как можно раньше. Оказывается, что этот алгоритм всегда дает оптимальное решение. Чтобы доказать это, рассмотрим, что произойдет, если сначала выбрать событие, которое заканчивается позже, чем событие, заканчивающееся первым. Тогда число вариантов выбора следующего события окажется никак не больше, чем если бы мы последовали предложенной стратегии. Следова- тельно, выбор события, заканчивающегося позже, никогда не даст лучше- го решения, и, значит, жадный алгоритм правилен. 4.2.3. Работы и сроки исполнения Наконец, предположим, что дано n работ и для каждой указаны продол- жительность и крайний срок. Наша задача – выбрать порядок выполнения работ. Для каждой работы нам начисляется d – x баллов, где d – крайний срок исполнения работы, а x – момент ее фактического завершения. Какое максимальное число баллов мы можем заработать? Предположим, что заданы такие работы: Работа Продолжительность Крайний срок A 4 2 B 3 10 C 2 8 D 4 15 4.3. Двоичный поиск 69 На рис. 4.12 показано оптимальное расписание работ в этом примере. При таком расписании за C начисляется 6 баллов, за B – 5 баллов, за A на- числяется 7 баллов, за D – 2 балла. Итого – 6 баллов. Рис. 4.12. Оптимальное расписание работ Оказывается, что оптимальное решение задачи вообще не зависит от крайних сроков, а правильная жадная стратегия заключается в том, чтобы выполнять работы в порядке возрастания продолжительностей. Действи- тельно, если в некотором решении сначала выполняется длинная работа, а за ней – более короткая, то решение можно улучшить, поменяв эти две работы местами. На рис. 4.13 показаны две работы X и Y продолжительностью a и b соот- ветственно. Изначально выполнение X запланировано раньше Y. Но, по- скольку a > b, работы следует поменять местами. Теперь за X начисляется на b баллов меньше, а за Y – на a баллов больше, поэтому общее число баллов увеличивается на a − b > 0. Таким образом, в оптимальном решении короткие работы всегда предшествуют длинным, поэтому работы следует отсортировать по продолжительности. Исходный порядок Переставленный порядок Рис. 4.13. Улучшение решения путем перестановки работ X и Y 4.3. Двоичный поиск Двоичный поиск – это алгоритм с временной сложностью O(log n), который, например, позволяет эффективно проверить, встречается ли в массиве заданное значение. В этом разделе мы сначала рассмотрим реализацию двоичного поиска, а затем посмотрим, как ей воспользоваться для нахож- дения оптимальных решений задач. 4.3.1. Реализация поиска Пусть дан отсортированный массив с n элементами, и мы хотим прове- рить, встречается ли в нем значение x. Мы обсудим два способа реализо- вать алгоритм двоичного поиска для решения этой задачи. 70 Глава 4. Сортировка и поиск Первый метод. Самый распространенный способ реализации двоич- ного поиска напоминает поиск слова в словаре 3 . Определено понятие ак- тивного подмассива, который первоначально содержит все элементы мас- сива. Алгоритм состоит из ряда шагов, на каждом из которых диапазон поиска делится пополам. На каждом шаге проверяется средний элемент активного подмассива. Если средний элемент совпадает с искомым зна- чением, то поиск заканчивается. В противном случае поиск рекурсивно продолжается в левой или правой половине подмассива в зависимости от значения среднего элемента. На рис. 4.14 показано, как в массиве ищется элемент со значением 9. Рис. 4.14. Традиционная реализация двоичного поиска. На каждом шаге проверяется средний элемент активного подмассива, и поиск продолжается в левой или в правой части Ниже приведена реализация поиска: int a = 0, b = n-1; while (a <= b) { int k = (a+b)/2; if (array[k] == x) { // x найден в позиции с индексом k } if (array[k] < x) a = k+1; else b = k-1; } В этой реализации активный подмассив занимает позиции с индексами в диапазоне a … b, а начальный диапазон равен 0 … n − 1. На каждом шаге 3 Некоторые люди, включая автора книги, все еще пользуются печатными словарями. Другой при- мер – поиск телефонного номера в печатном телефонном справочнике – выглядит еще более древ- ним. 4.3. Двоичный поиск 71 алгоритм уменьшает размер массива вдвое, так что временная сложность составляет O(log n). Второй метод. Другой способ реализации двоичного поиска заключа- ется в том, чтобы просматривать массив слева направо, совершая прыжки. Начальная длина прыжка равна n/2, и на каждом шаге она уменьшается вдвое: n/4, n/8, n/16 и т. д., пока, наконец, не станет равна 1. На каждом шаге очередной прыжок совершается при условии, что мы не приземлим- ся за пределами массива или на элементе, значение которого превышает искомое. После всех прыжков либо искомый элемент будет найден, либо он заведомо не встречается в массиве. На рис. 4.15 показано применение этого метода на конкретном примере. Рис. 4.15. Альтернативная реализация двоичного поиска. Мы просматриваем массив слева направо, перепрыгивая через элементы Ниже приведена реализация: int k = 0; for (int b = n/2; b >= 1; b /= 2) { while (k+b < n && array[k+b] <= x) k += b; } if (array[k] == x) { // x найден в позиции с индексом k } Здесь переменная b содержит текущую длину прыжка. Временная слож- ность алгоритма равна O(log n), потому что код в цикле while выполняется не более двух раз для каждой длины прыжка. 4.3.2. Двоичный поиск по ответу Пусть мы решаем некоторую задачу, и существует функция valid (x), возвращающая true , если x – допустимое решение, и false в противном 72 Глава 4. Сортировка и поиск случае. Кроме того, мы знаем, что valid (x)равно false , когда x < k,и равно true , когда x ≥ k. В такой ситуации можно использовать двоичный поиск для эффективного нахождения k. Идея в том, чтобы с помощью двоичного поиска найти наибольшее значение 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; Начальная длина прыжка z должна быть верхней границей ответа, т. е. любым значением, для которого точно известно, что valid (z)равно true Алгоритм вызывает функцию valid O(log z)раз, поэтому время работы зависит от функции valid . Так, если эта функция работает время O(n), то сложность алгоритма равна O(n log z). Пример. Рассмотрим следующую задачу: нам нужно выполнить k зада- ний на n машинах. Каждой машине i сопоставлено целое число p i – время выполнения одного задания. За какое минимальное время можно обрабо- тать все задания? Пусть k = 8, n = 3, а времена обработки p 1 = 2, p 2 = 3, p 3 = 7. В этом случае минимальное общее время обработки равно 9, как следует из плана, пока- занного на рис. 4.16. Машина 1 Машина 2 Машина 3 Рис. 4.16. Оптимальное планирование обработки: машина 1 выполняет четыре задания, машина 2 – три задания, машина 3 – одно задание Назовем valid (x)функцию, которая определяет, можно ли обработать все задания, используя не более x единиц времени. В нашем примере valid (9), очевидно, равно true , что доказывается планом на рис. 4.16. С другой сто- роны, valid (8) должно быть равно false , потому что минимальное время обработки равно 9. Вычислить значение valid (x)легко, потому что каждая машина i может выполнить не более ⌊x/p i ⌋ заданий за x единиц времени. Следовательно, 4.3. Двоичный поиск 73 если сумма всех ⌊x/p i ⌋ равна k или больше, то x – допустимое решение. Да- лее мы можем применить двоичный поиск, чтобы найти минимальное значение x, для которого valid (x)равно true Насколько эффективен получившийся алгоритм? Вычисление функции valid занимает время O(n), поэтому алгоритм работает за время O(n log z), где z – верхняя граница ответа. Одно из возможных значений z равно kp 1 , оно соответствует решению, в котором все задания выполняет первая ма- шина. Очевидно, что это действительно верхняя граница. |