Самостоятельная работа №1 По предмету: Алгоритмы проектирования Статические и динамические меры сложности алгоритма

1.2. Оценки сложности алгоритмов
Для оценки сложности алгоритмов существует много критериев. Чаще всего нас будет интересовать порядок роста необходимых для решения задачи времени и емкости памяти при увеличении количества входных данных. Свяжем с каждой конкретной задачей некоторое число, называемое ее размером, которое выражало бы меру количества входных данных. Например, размером задачи умножения матриц может быть наибольший размер матриц сомножителей; размером задачи о графах может быть число ребер данного графа, и т.п.
Время, затрачиваемое алгоритмом, как функция размера задачи, называется временной сложностью этого алгоритма. Поведение этой сложности в пределе при увеличении размера задачи называется асимптотической временной сложностью. Аналогично определяется емкостная сложность и асимптотическая емкостная сложность.
Именно асимптотическая сложность алгоритма определяет в итоге размер задач, которые можно решить этим алгоритмом. Если алгоритм обрабатывает входы размера n за время Cn², где C - некоторая постоянная, то говорят, что временная сложность этого алгоритма есть O(n²)(читается “порядка n^2" ). Точнее, говорят, что (неотрицательная) функция g(n) есть O(f(n)), если существует такая постоянная C, что g(n)Cf(n) для всех, кроме конечного (возможно пустого) множества неотрицательных значений n.
Временная сложность в худшем случае (или просто временная сложность) РАМ-программы - это функция f(n), равная наибольшей (по всем входам размера n) из сумм времен, затраченных на каждую сработавшую команду.Временная сложность в среднем - это среднее, взятое по всем входам размера n, тех же самых сумм.
Аналогично определяется понятие для емкости памяти, только вместо "времен, затраченных на каждую сработавшую команду", следует подставить "емкостей всех регистров, к которым было обращение".
Чтобы точно определить временную и емкостную сложность, надо указать время, необходимое для выполнения каждой РАМ-команды, и объем памяти, используемой каждым регистром. Мы рассмотрим два весовых критерия для наших программ.
Определение1. При равномерном весовом критерии каждая РАМ-команда затрачивает одну единицу времени и каждый регистр использует одну единицу памяти. Если не оговорено противное, то сложность РАМ-программы будет измеряться в соответствии с равномерным весовым критерием.
Определение2. Логарифмическим весовым критерием,называется логарифмическая функция l(i) на целых числах i, заданная равенством:


(*)
Это определение принимает во внимание ограничение размера реальных ячеек памяти.
В таблице 2.8 приведены логарифмические веса t(a) для всех трех возможных видов операнда a ;в таблице 2.9 приведены веса некоторых РАМ-команд.

Таблица2.9

N^0	Команда	Вес команды
1	LOAD a	t(i)
2	ADD *a	l(c(0))+t(a)
3	REAL i	l(вход)+l(i)
4	REAL *i	l(вход)+l(i)+l(c(i))
5	HALT	1

Таблица2.8

Операнд а	Вес t(a)
=i	l(i)
i	l(i)+l(c(i))
*i	l(i)+l(c(i))+l(c(c(i)))

В () учитывается, что для представления целого числа n в регистре требуется log n+1 битов. Регистры же могут содержать произвольно большие целые числа.

Логарифмический весовой критерий основан на грубом допущении, что цена выполнения команды (ее вес) пропорциональна длине ее операндов.
Рассмотрим для примера вес команды ADD *i. Сначала мы должны определить трудность декодирования операнда представленного адресом. Просмотр целого числа i занимает время l(i). Затем, чтобы прочитать содержимое c(i) регистра i и найти его местоположение, понадобится время l(c(i)). На конец, считывание содержимого c(i) требует время l(c(c(i))). Так как команда ADD *i прибавляет целое число c(c(i)) к целому числу c(0) в сумматоре, то ясно, что разумным весом, который следует придать команде ADD *i, является l(c(0)+l(i)+l(c(i))+l(c(c(i)))).
Некоторая программа может иметь существенно различные временные сложности в зависимости от того, какой используется весовой критерий - равномерный или логарифмический. Если разумно предположить, что каждое число, встречающееся в задаче, можно хранить в виде одного машинного слова, то годится равномерная весовая функция. В иной ситуации для реалистического анализа сложности более подходящим может оказаться логарифмический вес.