Перебор

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

Схема перебора всегда будет одинакова:

во-первых, надо установить в каком порядке будут перебираться заданные элементы (в частности, определить, какой из них будет первым, а какой последним);

во-вторых, научиться переходить от произвольного элемента к следующему за ним (т.е. для заданного элемента x1 строить такой элемент x2, что x1<x2 и между x1 и x2 нет других элементов).

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

Немного о терминологии.

Символ o()

Определение. Функция f(x) называется O большим от функции g(x) (пишется f(x)=O(g(x))), если существуют числа C и x₀ такие, что для всех x>x₀ выполняется условие f(x)<Cg(x).

В олимпиадном программировании часто пишут, что время работы алгоритма равно O(f(x)), где x - величина, связанная с размером входных данных (например, размер входного массива). Это фактически означает, что порядок времени работы алгоритма не превышает порядка функции f(x). Использование такого способа оценки времени работы алгоритмов связано с тем, что, в отличие от физического времени работы, порядок времени работы алгоритма не зависит от компилятора, процессора и операционной системы компьютера, на котором он выполняется. К сожалению, такая оценка не всегда дает правильное представление о реальном времени работы алгоритма; некоторые алгоритмы с плохой асимптотикой имеют маленькую константу и работают быстрее алгоритмов с хорошей асимптотикой и большой константой (например, в некоторых случаях алгоритм Эдмонда-Карпа, работающий за O(NM²), ищет максимальный поток в сети быстрее алгоритма "поднять и в начало" со временем работы O(N³), а алгоритм Дейкстры в простейшей реализации со временем работы O(N²+M) работает, как правило, быстрее реализации того же алгоритма с помощью фибоначчиевых куч, хотя асимптотика такого варианта O(Nlog N+M)).

Известно, что

• если f(x)=O(g(x)) и g(x)=O(h(x)), то f(x)=O(h(x))

• f(x)+g(x)=O(max(f(x),g(x))

• Cf(x)=O(f(x)), где C - константа

• xⁿ=O(x^m), если n<=m

• xⁿ=O(m^x)

• m^x=O(x^x)

• log x=O(x)

• log(x!)=O(xlog x)

• Если время работы алгоритма O(x), то алгоритм называется линейным

• Если время работы алгоритма O(xⁿ) для некоторого фиксированного n, то алгоритм называется полиномиальным

Асимптотическое соотношение показывает, как быстро будет расти время работы алгоритма при больших x, что весьма важно. Пусть, например, у нас есть два алгоритма, один из которых работает за время f(x)=x², а второй за время g(x)=10000x. Ясно, что f(x)=O(x²), g(x)=O(x). При малых x f(x) будет намного меньше g(x), но уже при x=100000, f(x)=10¹⁰, а g(x)=10₉<f(x), и при увеличении x разница между этими двумя функциями будет быстро расти.