Шаг алгоритма

Остается еще объяснить точнее, что мы понимаем под «шагом» алгоритма. Пусть наши программы транслируются на машинный язык типичной ЭВМ. Причем ЭВМ имеет наборе своих команд команды переноса слова из памяти в буфер и наоборот, арифметические операции сложения, вычитания, умножения и деления, условные переходы, операции ввода-вывода, а также косвенной адресации, выполненной аппаратно (т. е. определение аргумента операции через адрес ячейки памяти, содержащей адрес этого аргумента).

Шаг алгоритма - это выполнение любой из указанных выше команд. При таком определении шага сложность алгоритма зависит от конкретного вида машинных команд. Однако нас никогда не будет интересовать точная сложность алгоритма, а только асимптотическая сложность, т. е. асимптотическая скорость увеличения числа шагов алгоритма, когда размерность задачи неограниченно растет (чтобы можно было поговорить о такой скорости роста, предполагаем, что объем памяти нашего компьютера неограниченный, а также, что каждая ячейка памяти может содержать произвольно большое целое число). Ясно, что при двух произвольных «разумных» способах трансляции соответствующие сложности различаются не более чем на мультипликативную постоянную, а их скорость роста одинакова.

Если сложность какого-либо алгоритма есть О(g(п)), то говорим, что этот алгоритм «затрачивает порядка О( g(п)) времени».

Подобным же образом определяются символы О(g(п₁,,п_k)) и Ω(g(п₁,,п_k)) для функции многих переменных, например:

f(п₁,,п_k) = О(g(п₁,,п_k)) существуют константы С, N > 0, такие, что f(п₁,,п_k) С g(п₁,,п_k) для всех п₁,,п_k N;

Определенную таким образом сложность иногда называют временной сложностью в отличие от сложности по памяти, определяющей величину объема памяти, использованного алгоритмом, как функцию размерности задачи.

Оптимизационные задачи

Мы будем рассматривать оптимизационные задачи. В таких задачах может существовать множество различных решений; их «качество» определяется значением какого-то параметра, и требуется выбрать оптимальное решение, при котором значение параметра будет минимальным или максимальным (в зависимости от постановки задачи).

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

Рассмотрим схему работы жадных алгоритмов на конкретных примерах.

---

Дата добавления: 2015-07-07