Трудоемкость алгоритмов

K-подмножества (сочетания)

Пусть задано множество {a₁, a₂, …, a_n}. Рассмотрим порождение в лексикографическом порядке подмножеств из k элементов, то есть сочетаний из n предметов по k штук. Как и ранее можно считать, что подмножество определяется последовательностью индексов располагаемых элементов, поэтому будем выбирать подмножества множества {1, 2, …, n}.

Например, трехэлементные подмножества множества {1, 2, 3, 4, 5, 6} записываются в лексикографическом порядке следующим образом:

123 135 234 256

124 136 235 345

125 145 236 346

126 146 245 356

134 156 246 456

Подмножества или сочетания в лексикографическом порядке можно порождать простым способом. Начиная с сочетания (1, 2, …, k) следующее сочетание находится просмотром текущего сочетания справа налево с тем, чтобы определить место самого правого элемента, который еще не достиг максимального значения. Этот элемент увеличивается на 1. Всем элементам справа от него присваиваются новые наименьшие возможные значения, которые должны быть больше данного элемента.

В предыдущих разделах мы уже не раз сталкивались с оценкой трудоемкости алгоритмов, то есть объема необходимых расчетов. Часто эта важнейшая характеристика алгоритмов недооценивается студентами.

Рассмотрим наглядный пример. Пусть требуется найти кратчайший путь на графе из 30 вершин, в котором каждая вершина связана со всеми другими. Как известно из начальной части курса, для решения этой задачи часто используют алгоритм Дейкстры, трудоемкость которого пропорциональна N ², где N – количество вершин графа. В математике для этого случая принято обозначение O (N ²).

Попробуем найти кратчайший путь перебором всевозможных путей, что проще всего реализуется поиском в глубину. Ограничимся для простоты только путями, включающими все вершины графа. Поскольку в промежутке между начальной и конечной вершинами могут в различном порядке находиться 28 вершин, то таких путей 28! Эта величина превышает 10²⁹. Будем считать, что мы в состоянии находить и оценивать 10⁹ путей в секунду (реально значительно меньше). Значит, нам потребуется 10²⁰ секунд для просмотра всех путей. В сутках менее 10⁵ секунд, а в году менее 500 суток, то есть поиск займет более 2´10¹² лет. И это при том, что мы рассматривали только самые длинные по числу вершин пути! Нас не спасет даже компьютер, работающий в 1000 раз быстрее.

Можно возразить, что кратчайший путь не должен включать так много промежуточных вершин. Но термин “длина” в задачах поиска путей на графе используется в обобщенном смысле. Например, речь может идти о стоимости самолетных сообщений. Легко вообразить, что перелеты на короткое расстояние совершают маленькие самолеты, билеты на которые обходятся дешевле.

В первую очередь оценивают зависимость трудоемкости вычислений от размерности исходных данных N. Переборные алгоритмы имеют обычно экспоненциальную трудоемкость, то есть объем вычислений оценивается как O(Exp(N)). Такие алгоритмы реализуемы только при ограниченных значениях N. Полиномиальные алгоритмы имеют оценку O(N^P), где P >0.

Величина коэффициента пропорциональности отступает на второй план в тех случаях, когда размерность велика. Сравним, например, два алгоритма с трудоемкостью 0.1´ N ² и 100´ N. При N < 1000 первый алгоритм эффективнее. Но при N = 10⁵ второй алгоритм в 100 раз быстрее первого.

Нередко одна и та же задача может решаться разными по эффективности алгоритмами. Нахождение более быстрых алгоритмов часто ведет к прорыву в различных проблемах, как теоретических, так и практических. Например, быстрые алгоритмы работы со строками лежат в основе поисковых систем Интернета.

Часто высокая скорость работы достигается путем использования рациональных структур данных. Так быстрый поиск информации в современных системах управления базами данных основан на Б-деревьях и хеш-таблицах.

Рассмотрим разные подходы к решению задач, которые существенно отличаются по трудоемкости.

Гомер Симпсон [18]. Обеденный перерыв Гомера Симпсона составляет T миллисекунд. Один гамбургер Гомер съедает за N миллисекунд, один чизбургер - за M (1 ≤ M, N, T ≤ 2×10⁹). Требуется найти максимальное суммарное число гамбургеров и чизбургеров, которые Гомер может съесть в течение обеденного перерыва. Предпочтителен вариант, когда дополнительного времени остаётся как можно меньше. Выдать остаток обеденного времени.

Максимальное число гамбургеров составляет K = T div N, а чизбургеров L = T div M. Двойной цикл до K и L по трудоемкости вычислений нас устроить не может.

В [18] указан следующий простой выход. Если съедается I гамбургеров, то число чизбургеров определяется как J = (T - I × N) div M. Значит, достаточно одинарного цикла.

Но и такой подход не годится для заданной размерности. Пусть, например, M ≤ N. Очевидно, что максимальное суммарное число гамбургеров и чизбургеров составляет P = T div M. Как минимизировать остаток времени? Нужно вместо части гамбургеров съесть чизбургеры. Каждый из них потребует N - M из остатка времени. Значит, их можно съесть Q = (T - P × M) div (N - M). Тогда число гамбургеров уменьшится и составит P - Q.

Для решения следующей задачи рассмотрим алгоритмы, существенно отличающиеся по трудоемкости.

Премия [17]. Жилищная контора решила наградить своего лучшего сантехника. Был составлен список балансовых сумм по N квартирам в виде целых чисел. Числа в списке пронумеровали от 1 до N. Известно, что должники имеют отрицательный баланс. Сантехник должен выбрать часть списка, указав начальный и конечный номера. Балансы, соответствующие этому диапазону номеров, суммируются. Полученное значение составляет величину премии сантехника. Требуется определить такие начальный и конечный номера, чтобы премия оказалась максимальной.

Ввод изфайла INPUT.TXT. Первая строка содержит значение N (1 ≤ N ≤ 100000). Во второй строке задаются через пробел балансы жильцов X₁,…, X_N (-1000 ≤ X_i ≤ 1000).

Вывод в файл OUTPUT.TXT. В первой строке выводится максимальная сумма ожидаемой премии. Во второй строке выводятся начальный и конечный номера списка, соответствующие полученной сумме. Если ответов несколько, то указывается пара с минимальным начальным номером, а при одинаковых начальных номерах – пара с минимальным конечным номером.

Ограничения. Время счета не более 1 с.

Дата добавления: 2014-01-11