Временной анализ алгоритмов
Одну и ту же задачу можно решить разными алгоритмами. Но в ряде случаев бывают проблемы: с одной стороны он должен быть простым, с другой решать быстро. Сравнивать алгоритмы имеет смысл, если они решают одну и ту же задачу. У нас основным критерием будет время. Основным критерием будет время выполнения алгоритма. Мы будем оценивать абсолютное число шагов, операций, необходимых на выполнение алгоритма (а не в реальном времени - секундах или минутах, так как аппаратные характеристики компьютера различны (на одной машине алгоритм может выполниться быстрее)). Наибольший интерес вызывает зависимость числа операций от конкретного алгоритма, от размера входных данных.
Число операций измеряет относительно время выполнения алгоритмов. Иногда будем использовать термин временная сложность алгоритма. Наряду с временной сложностью есть и другие критерии: по трудоемкости, по использованию памяти.
Под размерностью задачи будем понимать количество входных данных.
Время, затрачиваемое алгоритмом как ф-я размера задачи называется временной сложностью этого алгоритма.
Поведение этой сложности в пределе при увеличении размера задачи наз-ся асимптотической временной сложностью. Именно асимптотическая сложность алгоритма определяет размер задачи.
Комментарий. n – размер входных данных. Алгоритм A быстрее алгоритма B при малых n, но при больших n ситуация может измениться.
Анализ алгоритмов даёт инструмент для выбора алгоритма f(n), но результат f(n) – не формула, а результат анализа, это некоторый обобщённый показатель количества времени, необходимого для решения задачи на массиве данных длины n.
Возьмём алгоритм подсчёта числа вхождения различных символов алфавита в файл.
for i:=1 to 256 do
обнулить счётчик [массив счётчик, каждая ячейка отвечает за количество вхождений i-го символа]
end for
while (в файле ещё остались символы) do
ввести очередной символ
увеличить на единицу счётчик
end while
Пусть имеется входной файл из n символов.
- Сперва инициализируется переменная цикла. Цикл инициализации делает 256 присваиваний для переменно цикла (i) и 256 для счётчика. 256 приращений переменной цикла. 257 проверок, что переменная i находится в пределах нашего цикла.
- n+1 проверка условий. n+1 приращение цикла. n+256 приращений. 257 присваиваний. n+258 проверок условий.
При n=500 происходит 1771 операций, причём 770 – операций инициализации (43%). При n=50000 произойдёт 100771 операций, и число операций инициализации будет мене 1% от общего числа операций. То есть при росте n процедура инициализации становится всё менее значительной.
Для содержательной работы часть инициализации становиться незначительной в общем объёме работы.
Не только абсолютное количество входных данных характеризует работу алгоритма.
Иногда полезным бывает относить алгоритмы к тому или иному классу:
1)самым полезным является класс O(f):
Мы говорим g принадлежит O(f) если существует c,n0 : для любого n>n0 g<=cf, тогда gпринадлежит O(f) lim g/f=c при n стремящ к +бесконечности
Пример g=x2 f=x3 можно говорить, что g принадлежит O(x3)
2)если класс
g принадлежит если существует c,n0 : для любого n>n0 g>=cf класс f задает нижнюю планку
3)есть класс где рассматривается ф-и одного порядка если g принадлежит lim g/f=const
Классы входных данных
Роль входных данных в алгоритмах велика, поскольку последовательность действий алгоритма определяется не в последнюю очередь самим составом входных данных.
Рассмотрим пример поиска максимального элемента вектора.
max:=v[1];
for i:=2 to n do if (v[i]>max) then max:=v[i];
n=10
Наилучший вариант, если max на первом месте, то будет только одно присваивание, а дальше сравнение. Наихудший вариант если стоит на последнем месте при упорядочении по возрастанию.
Если на любом другом месте. Таких вариантов 10! (возможные перестановки).
Пусть max на 2м месте, а остальные не важно, след-но весь обзор нам не нужен => кол-во перестановок других элементов сократится в 10 раз. Теперь можно рассматривать, когда элемент находится на 3м месте и просчитать кол-во операций. Это средний случай. Т.о. выделяем 10 различных классов.
Эти классы и будут образовывать классы входных данных.
Наилучший случай – такой набор данных, при котором алгоритм выполняет наименьшее число действий. Анализ наихудшего случая чрезвычайно важен, так как он позволяет представить максимальное время работы алгоритма. Анализ наихудшего случая даёт верхние оценки для времени работы частей нашей программы в зависимости от алгоритмов. И именно при анализе таких случаев оценивают сложность задачи.
Анализ среднего случая является самым сложным в смысле учёта многих параметров. В основе анализа лежит определение различных групп, на которые следует разбивать различные наборы входных данных. На втором шаге определяется вероятность с какой входной набор принадлежит каждой группе. На третьем шаге подсчитывается время работы на данных из каждой группы. Время работы на данных одной группы должно быть одинаково, иначе они не из одной группы.
, где n-размер входных данных, m-число групп, pi –вероятность того, что входные данные принадлежат группе с номером i, ti –время, необходимое алгоритму для обработки данных из группы с номером i. И вероятность и время и число групп непосредственно зависят от n.
Записали алгоритм, что считать при определении времени алгоритма?
На первом этапе выбирается значимая операция или группа операций, а на втором – какие из этих операций содержатся в теле алгоритма, а какие учавствуют на ввод, учет, регистрацию данных. Все операторы функции считаются эквивалентными и их учитывают в алгоритмах поиска и сортировки.
Две группы операторов: аддитивные операторы – сложение, вычитание и мультипликативные операторы – умножение, деление, остаток от деления. Разбиение связано с тем, что сложение быстрее умножения. На практике в большинстве случаев выполнению этих операций присваивается время=const и присваивается время=1.
При анализе алгоритма или программы надо учитывать:
- если создаваемая программа будет использована только несколько раз, тогда стоимость отладки и описания программ будет доминировать в общей стоимости. В этом случае вывод: следует предпочесть алгоритм, наиболее простой для реализации.
- эффективные, но сложные алгоритмы могут лишь быть нежелательными, если готовые программы будут поддерживать лица, не участвовавшие в написании этих программ.
- некоторые алгоритмы требуют таких больших объемов оперативной памяти, но этот факт сводит на нет преимущества эффективного алгоритма.
Пример: Алгоритм поиска по списку list из N элементов. Программа ищет элемент в списке, если находит, то выводит номер элемента и заканчивается, иначе выведет 0.
search (list, target, n);
begin
for i=1 to n do
if (target=list[i]) then return I;
return 0;
end;
Наилучший случай, когда целевой элемент на первом месте. Худший случай, когда искомый элемент на последнем месте (все сравнения происходят). Средний - элемент внутри массива. Наихудший очень важен, т.к. по нему оценивается сложность задачи. В среднем надо разбивать на группы, в каждую группу элемент входит с одной вероятностью, определяющей время работы алгоритма на группе.
Рассмотрим пример: Какова вероятность нахождения элемента на N-ом месте (элементов N)
рi=1/N О(1)- класс единицы, константы.
1. если на первом месте, один оператор сравнения. Время работы =1
2.на втором месте оператор сравнения 2 раза. Время=2
….
На i-м месте i
На N месте N
.
T(N) принадлежит классу O((N+1)/2)
Все алгоритмы поиска относятся к классу O(N) (поиск м.б. последовательным и с помощью бинарного дерева).
Степенные ф-и можно отнести к классу полиномиальных ф-й принадлежащих Р(n).
Вычисление времени выполнения программы
Теоретическое вычисление времени выполнения программ – трудная задач. На практике всё легче, но надо знать основные принципы. Рассмотрим, как выполняются операции сложения и умножения с использованием O-символики.
Правило сложения
T1(n) и T2(n) – время выполнения двух программных фрагментов p1 и p2. T1(n) = O(f(n)) – T1 имеет степень роста O(f(n)). T2(n) = O(g(n)). T1(n)+T2(n) оцениваются как O(max [f(n), g(n)]).
.
◄ c1 и c2=const, n1, n2 при n>=n1 выполняется соответствие T1(n)<=c1f(n). При n>=n2: T2(n)<=c2g(n).
max[n1,n2]=n0. Тогда при n>n0 T1(n)+T2(n)<=(c1+c2)max[f(n),g(n)] ►
Правило произведения
T1(n) и T2(n) – время выполнения двух программных фрагментов p1 и p2. T1(n) = O(f(n)) – T1 имеет степень роста O(f(n)). T2(n) = O(g(n)). Тогда произведение T1(n)T2(n) оценивается как O(f(n)g(n)).
Пример на сложение: Правило суммирования используется для вычисления времени последовательного выполнения программных фрагментов. Пусть имеется три фрагмента O(n2), O(n3), O(nlog(n)). Тогда T1(n)+T2(n)+T3(n)=O(n3).
В общем случае время выполнения программных фрагментов имеет порядок фрагмента с наибольшим временем выполнения. Бывают случаи, когда порядок роста одного не соизмерим с другим.
Казалось бы парадоксальные вещи: O(cf(n)) O(f(n)), O(n2/2) O(n2).
Сложные классы задач
Класс P – это задачи с полиномиальной сложностью. Задача называется полиномиальной, если существует k и алгоритм решающий эту задачу за время O(nk), где n – длина входа (размер входных данных). Класс задач P определяется через существование полиномиального по времени алгоритма её решения. При этом предполагается худший случай по времени для всех входов длины n.
Задачи класса P – интуитивные задачи, решаемые за реальное время. При этом k<6 – для задач реального времени. Преимущество в том, что он инвариантен по модели, то есть в независимости от входных данных модель не меняется. Класс P обладает свойством замкнутости, то есть сумма и произведение полиномов – есть полином.Есть задачи, не относящиеся к классу P: задачи раскраски графа. Каждую вершину графа надо окрасить так, чтобы ни одна её соседняя вершина не имела такой же цвет. (Задачи могут ставиться – найти наименьшее количество используемых цветов, например – 2). Путь решения вполне определенный-осуществить переборс учетом требований. Если мы возьмем nвершин и n цветов, то будет n! Не полиномиальный класс.
Задача коммивояжера:
c=[c(1),…,c(m)]. d(c(i),c(j)) – расстояние между городами. <СП,…, СП> - «П» означает, что города идут по нужному порядку. Решение данной задачи достигается перебором. Для n городов будет n! переборов. Такие задачи относятся к факториальным или O(xn), n>2.
Единственный способ реализации таких задач – оптимальный алгоритм реализации. Эти задачи необходимо решать за реальное время. (Пример раскраски графа – составление расписания экзаменов).
Эти задачи подходят под класс NP – недетерминированные полиномиальные (недетерминированный полиномиальной сложности). Это объясняется тем, что мы имеем двухшаговый подход на первом недетерминированном шаге мы пытаемся угадать решение, найти его вариант, при этом используются свойства задачи, то есть ищется не самое оптимальное, а близкое к нему. На втором шаге проверяется действительно ли ответ, полученный на первом шаге является решением задачи. Каждый из этих шагов относится к полиномиальному алгоритму (и 1-ый и 2-ой: выборка и проверка). Проблема в том, что не известно сколько раз нужно повторить эти шаги. Число обращений может оказаться экспоненциальным или факториальным. Этот процесс можно отнести к решению задачи коммивояжера:
1шаг (упорядочение городов) генерировать случайным образом упорядочение городов. Это недетерминированный процесс. На каждом шаге будет получаться новый порядок. Временная сложность O(n).
2шаг: происходит подсчет стоимости. Этот процесс имеет сложность O(n). Оба шага полиномиальны, но времяёмкой ее делает неизвестное число итераций этой процедуры. Эта задача относится к NP классу.
Существует набор задач относящихся к NPC – недетерминированные полные задачи.
Один из способов решения задачи – свести одну задачу к другой, тогда алгоритм решения второй задачи можно преобразовать так, чтобы он решал первую. Если вторая задача решается за полиномиальное время, то и наша тоже будет решаться за полиномиальное время. Однако редукция задач может оказаться более сложной.
При обсуждении класса NP задач следует иметь ввиду, что наше мнение – что их решение требует большого времени исходит из того, что мы не нашли эффективного алгоритма их решения. А что же такое класс NPC. Термин NP-полное относится к самым сложным задачам NP. Эти задачи выделяются тем, что если нам все-таки удастся найти полиномиальный алгоритм какой-либо из них, то это будет означать, что все задачи класса NP допускают полиномиальный алгоритм решения. Достаточно найти полиномиальный алгоритм для одной из них и тогда все они будут решаться полиномиально.
Доказывается, что задача относится к NP-полной, если удастся свести задачу к NP-полной.
Кук в 1971 году доказал задачу о конъюнктивно нормальной форме. Редукция – такая мощная вещь, что если бы одну NPC задачу можно было бы свести к NP, то все NPC можно было бы свести к NP.
Задачи: раскраска графа, раскладка по ящикам (груз раскладывается по ящикам- нужно использовать наименьшее число ящиков), упаковка рюкзака(задача в том, что нужно упаковать рюкзак такими вещами, что бы их стоимость была наибольшей), сумма элементов подмножетсв.
Соотношение между классами P и NP задач: PNP, хотя возможно существует и обратное включение, но пока не найдено алгоритмов.
