SHPORA.net :: PDA

Login:
регистрация

Main
FAQ

гуманитарные науки
естественные науки
математические науки
технические науки
Search:
Title: | Body:

Вычислит сложность алоритма

2.4 Вычислительная сложность алгоритма
2.4.1 Понятие сложности алгоритма

Пусть А ? алгоритм решения некоторого класса задач.
Назовем размерностью задачи (n) совокупность параметров (их количество), характеризующих объем обрабатываемых исходных данных и определяющих необходимые для выполнения расчетов ресурсы (время, память).
Например : Машина Тьюринга ? n ? длина цепочки, граф ? n ? количество вершин.
С понятием размерности задач связано понятие вычислительной сложности. Различают временную и емкостную сложность алгоритма.
Временная сложность - Т(n) ? функция , зависящая от размерности задачи время выполнения А.
Емкостная сложность ? С(n) ? функция, зависящая от размерности задачи ? необходимая память.
Технические характеристики ЭВМ при таком подходе не учитываются.
Оценивая вычислительную сложность ориентируются на количество основных операций (сложение, сравнение и т.д.), которые должен выполнить алгоритм для решения каждой задачи размерности n.
Можно рассмотреть 3 варианта оценки вычислительной сложности :
1) в ?худшем случае? - в процессе расчетов учитывается самая длинная последовательность основных операций.
2) В ?лучшем случае? - как правило это вырожденные ситуации.
3) В ?среднем? - для расчета которых необходимо иметь статистические данные о том как часто реализованы ?лучшие? и ?худшие? варианты.
Будем говорить , что f(n) и g(n) одного порядка для больших n: f(n)=О(g(n)), если
Например : f(n) = 2n5 + 6 n4 + 6 n2 +18 = O (n5), g(n)= n5.

Будем говорить, что f(n) имеет меньший порядок для больших чем g(n), если
Например : f(n) = 2n5 + 6 n4 + 6 n2 +18 = 0 (n6).
Причина использования оценок в форме О и 0 связана с тем, что точные зависимости при расчете сложности алгоритма зависят от особенностей реализации алгоритма и требуют вычислений лишних для поставленной задачи.
При достаточно больших n константы в формулах не оказывают влияния на порядок возрастания, но если константы сравнимы по порядку с n, то в каком-либо диапазоне данных это может привести к изменению эффективности алгоритма.

С точки зрения эффективности все алгоритмы делят на 2 класса: полиномиальные и экспоненциальные.
А ? полиномиальный, если f(n) растет не быстрее, чем полином k степени от n ТА(n) = О(Р k(n)), иначе А ? экспоненциальный.

Пример
полиномиальные: линейные О(n)
полулинейные О(n log n)
квадратичные О(n2)
экспоненциальные: О(n!) = О(n n)

Большинство экспоненциальных алгоритмов ? это варианты полного перебора, полиномиальные алгоритмы можно построить лишь тогда, когда удается найти решение без перебора всех допустимых вариантов данных.
Назовем классом Р-задач, задачи, для которых существует детерминированный алгоритм, реализующий эту задачу за полиномиальное время.
Задача называется труднорешаемой, если для ее решения не существует полиномиального алгоритма.
Класс задач, для решения которых существует недетерминированный алгоритм, решающий эту задачу за полиномиальное время , называется классом NP задач.


Модель недетерминированного алгоритма



Варианты исчерпаны

вариант решения решение




Класс Р ? задач входит в класс NP задач: Р NP (алгоритм А ? пустой). NPР являются труднорешаемыми.
В классе NP содержатся NP- полные задачи, для которых не существует детерминированного алгоритма, работающего за полиномиальное время.
Так как алгоритм решения NP задач состоит из алгоритма угадывания и алгоритма проверки, NP- полные задачи требуют полного перебора и решаются рекурсивно так, что алгоритм поиска решения на каждом шаге рассматривает все возможные варианты решений на глубине 1 и решает оставшуюся задачу меньшего размера.

Примеры NP- полных задач
1) генерация всех k-элементных подмножеств какого-либо n-элементного множества

2) построение разбиений множества из n?элементов на k1, k2, ? km?элементные подмножества

3) задача коммивояжера: коммивояжер должен посетить n городов так, чтобы максимально снизить расходы на поездку TA(n) = О (n!)
4) построение таблиц значений логарифмических функций TA(n) = О( 2n )

2.4.2 . Методы оценивания вычислительной сложности.

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

Оценка сложности на уровне блок-схем

Блок - схема - направленный граф, содержащий вершины 3-х типов :

1) Функциональная


2) Предикатная P


3) Объединяющая

Структурная блок-схема представляется в виде композиции четырех элементарных, называемых структурами управления:


1) композиция К




2) альтернатива А






3) итерация с постусловием I






4) итерация с предусловием



Использование 1) ? 4) достаточно для любого представления алгоритма, однако это будет не всегда просто и естественно, так как существует большее разнообразие структур.
Применяя вышесказанное, можно записать временную сложность в таком виде:
1) Т(К) = Т (F 1) + Т (F 2)
2) Тх(А) = Тх(Р) + max { Тх (F 1) , Тх (F 2) }
Тср(А) = Тср(Р) + Р1 Тср (F 1) + Р2 Тср (F 2)
Р1 и Р2 ? вероятности перехода по каждой дуге от Р

3) , 4) для каждого повторения: Тх(РF)= Тх(Р) + Тх(F), учитывая m повторений: Тх(I)= m Тх(РF)
Пусть f(n) ? зависимость чисел повторяющегося цикла от размерности задачи, если число операций в цикле оценивается константой с, то Тц1 = О(f(n)). В простейшем случае, когда просто просматривается путь длины n Тц = О(n).
Если имеется двойной цикл, причем число повторений внешнего f1(n), а внутреннего f2(n), то Тц2 = О(f1(n)*f2(n)).
Если параметр внутреннего цикла зависит от внешнего, например
for i := 1 to n do
for j:= j +1 to n do ?
Тогда:
i = 1 - внутренний цикл выполняется (n ? 1) раз
i = 2 - внутренний цикл выполняется (n ? 2) раз
. . .
i = n - внутренний цикл выполняется 0 раз

общее число повторов (n ? 1) + (n ? 2) + ? 1 + 0 = О(n2)

Оценка сложности на уровне моделей.

Такой вид оценок применяется в случае сложных программ, когда подробная блок?схема затрудняет вычисление оценок из-за громоздкости, тогда удобней оценить алгоритм глядя как бы сверху, т.е. на модель алгоритма.
Рассмотрим в качестве примера рекурсивный алгоритм.
Задача 1
Разместить слова длины h, использующие k букв в словаре. Модель ? дерево Число выходящих ребер из каждой вершины ? число способов выбора очередной буквы слов (т.е. число букв в алфавите). Каждый кольцевой вершине соответствует одно слово. Высота дерева ? h. Поиск слова ? обход дерева в прямом порядке.
Алгоритм WORD (h)
1. Найти множества слов, у которых совпадают первые буквы.
2. Исключить первую букву в каждом подмножестве слов.
3. Выполнить WORD (h-1) для укороченного слова
ТWORD(h)=(Т1+Т2)Т3=(k + const)·Т(h - 1)
Начальное условие: Т(1) = 1, решая уравнение получаем ТWORD(h) = О (k h)

Задача 2
Составить всевозможные неупорядоченные пары из n-элементов последовательности {а1,?а n }
1. i = 2 до n сформировать пары вида {а1,а. i }
2. исключить а1 из последовательности
3. выполнить алгоритм для последовательности {а2,?а n }

Т1 = n ? 1, Т2 = const Т3 = Т (n ? 1)
Т(n) = n + const + Т(n ? 1) , Т(1) = 0 ==>
Т(n) = n + c + ( n + c + Т(n ? 2)) = 2 n + const + Т(n ? 2)
Т(n) = (k + 1) n + с + Т(n ? (k + 1))
Т(n) = (n ? 1) · n + с + Т(n ? (n ? 1)) = О(n2)

Итак, количество операций вычислялось без использования блок?схем. Важно было только определить, как представить задачу размерности n через подзадачи меньшей размерности.
Алгоритмы, основанные на таком принципе (разбиение на задачи меньшей размерности) моделируются с помощью деревьев.
Сформулируем теорему, определяющую один из возможных путей построения эффективного алгоритма, использующего этот принцип:
Теорема
Пусть имеется алгоритм для решения задачи размерности n, причем это решение конструируется из решений a подзадач размерности n/c алгоритмом перехода, оценивающимся сложностью O(n), тогда Т(n) = а · Т (n/c) + О(n), при начальном условии Т(1) = b.
Решение этого уравнения определяется в зависимости от а и с.