18. Временная и вычислительная сложность алгоритмов.

Временная сложность алгоритма (T(N), где N – размер задачи) – это

время выполнения алгоритма, измеренное в шагах (инструкциях алгоритма,

которые нужно выполнять для достижения результата). Т. е. это – число

элементарных операций, из которых складывается алгоритм решения задачи

(:=, <>, =, +, –, *, /; and, or, not, xor; call, return).

Различают три разновидности временной сложности, которые зависят от

комбинации входных данных при решении задачи (равнозначность,

разряженность, упорядоченность и др. свойства входных данных).

Worst Case – максимальное время выполнения (наихудший возможный

случай).

Average Case – среднее время выполнения (в статистическом смысле).

Best Case – минимальное время (наилучший случай).

На практике оперируют максимальным временем выполнения алгоритма.

Пример 1:

Сложность алгоритма умножения матрицы на вектор порядка N может

быть записана:





* 2

( * )

( )

C N

C M N

T N

Случай T(N)=C*N2 применим для квадратной матрицы.

Элементарные операции в данном случае – совокупность «+» и «*».

Если исходная матрица – единичная, то получаем Best Case.

Если в матрице половина элементов – 0, половина – 1, то получаем

Average Case.

Константа С, которая не может быть точно выражена, характеризует

влияние внешних факторов на время выполнения алгоритмов

(быстродействие ЭВМ, скорость компиляции). Поэтому использование единиц

времени для оценки временной сложности алгоритмов не совсем корректно. В

26

этом случае говорят, что временная сложность алгоритма умножения

матрицы на вектор пропорциональна N2.

27

19. Понятие р- и np-задач.

В зависимости от значений функции f(N) различают следующие классы

алгоритмов:

1) Задачи, для которыхf

(N)=aN (линейная сложность)

Примеры: топологическая сортировка, отыскание остовного дерева и

связанных компонент дерева.

2) Задачи, для которых f(N) является нелинейной, но не более чем

полиномиальной

f(N)=Nm, m2

Примеры: умножение матриц, нахождение кратчайшего пути в дереве,

нахождение минимума остовных деревьев.

3) Задачи, о которых нельзя сказать, что они обязательно имеют

экспоненциальную сложность, но для которых не известны быстрые

алгоритмы, требующие менее, чем kn операций.

Примеры: задача коммивояжера (TSP), определение изоморфизма,

алгоритм нахождения максимальной клики в графе.

4) Задачи с обязательной экспоненциальной сложностью

f(N)=KN , K2

Для этого класса не существует быстрых алгоритмов.

Примеры: прохождение всех остовных деревьев графа, всех его циклов и

всех клик.

Для таких задач невозможно открыть новый алгоритм с меньшей

сложностью.

Замечание: Для 3-го класса задач существуют теоретические

предпосылки разработки эффективных алгоритмов с полиномиальной

сложностью (класса 2), но которые пока не найдены. Разработка

полиномиального алгоритма для любой из задач 3-го класса автоматически

означала бы решение всех задач этого класса за полиномиальное время.

Полиномиальный алгоритм – это алгоритм с полиномиальной

трудоемкостью (временем работы).

Полиномиальный или экспоненциальный характер работы алгоритма

инвариантен относительно формы представления входных данных (двоичная,

десятичная или другая система счисления).

Говорят, что алгоритм является полиномиальным, если время его

работы, т. е. временная сложность, ограничивается сверху полиномом

некоторой степени T(N)=O(Nm). Тогда все задачи, которые решаются таким

алгоритмом, образуют Р-класс задач. Говорят, что эти задачи входят в Р.

Задачи, временная сложность которых экспоненциальна (T(N)=O(KN)), не

входят в Р.

Замечание: Можно показать, что задачи с линейной сложностью входят в

Р

T(N)=O(N1)

28

Введем класс NP-задач, которые можно решить за полиномиальное

время с помощью недетерминированного алгоритма.

Определим состояние алгоритма как совокупность адреса выполняемой в

данный момент команды и значений всех переменных, что эквивалентно

вектору состояния процесса. Поэтому большинство алгоритмов являются

детерминированными, т. е. в них для любого состояния существует лишь

одно допустимое следующее состояние (включая операции условия и

выбора). Это значит, что такой алгоритм в каждый момент времени может

делать что-то одно.

В недетерминированном алгоритме (НДА) для любого данного

состояния может быть больше одного допустимого следующего состояния, т.

е. такой алгоритм в каждый момент времени может выполнить больше одного

оператора.

НДА не является случайным или вероятностным алгоритмом. Он

представляет собой алгоритм, который может находиться во многих

состояниях (это эквивалентно параллельному решению задачи с множеством

вариантов).

Пример:

Детерминированный алгоритм (ДА) решал бы эту задачу

последовательно (перебор всех вариантов, сравнение с критерием

оптимальности K0 до тех пор, пока не выберет альтернативу А0).

НДА может одновременно (параллельно) получить все альтернативы и

сравнить с K0, копируя самого себя в виде отдельного процесса для каждой

альтернативы, которая выполняется независимо.

При этом если какая-либо копия обнаружит, что получен неправильный

результат или результат не получен, то она прекращает свое исполнение.

Если же копия находит решение, удовлетворяющее K0, то она объявляет об

успехе, и все другие копии прекращают работу.

Т. о. НДА характеризуется тремя параметрами:

1. выбор – многозначная функция, значения которой являются

элементами множества S;

2. неудача заставляет копию алгоритма прекратить работу;

3. успех заставляет все копии алгоритма прекратить работу и

сформировать результат.

Очевидно, что никакое физическое устройство не способно на

неограниченное недетерминированное поведение, значит, НДА является

теоретическим методом.

29

ГА

ВК

ВА ПЗ

Ai A0

K0

Задачи, которые можно решить с помощью полиномиального НДА,

образуют класс NP-задач.

30

20. NP-трудные и NP-полные задачи.

Задача, входящая в Р, является NP-трудной, если существует

полиномиальный ДА (ПДА) ее решения, который можно использовать для

получения решения всех задач, входящих в NP. Т. е. такая задача является

NP-трудной, если она, по крайней мере, так же трудна, как любая задача,

входящая в NP.

NP-трудная задача, принадлежащая NP, называется NP-полной задачей.

Такие задачи не менее трудны, чем любая задача из NP. При этом

существование ПДА для NP-трудной или NP-полной задачи означает, что

классы Р и NP совпадают, т. е. возможно решение всех задач 3-го класса

быстрым алгоритмом.

Для доказательства того, что задача является NP-трудной, необходимо

показать, что если для задачи существует ПДА, то его можно использовать

для получения другого ПДА решения задач, входящих в NP.

Чтобы установить, что задача является NP-полной, необходимо доказать,

что она принадлежит NP.

Идея использовать алгоритм решения одной задачи для получения

алгоритма решения другой является одной из наиболее важных в теории

алгоритмов.

Определение 1: Задача Р1 преобразуется в задачу Р2, если любой

частный случай задачи Р1 можно преобразовать за полиномиальное время в

некоторый частный случай задачи Р2. Тогда решение Р1 можно получить за

полиномиальное время из решения частного случая задачи Р2.

Если Р1Р2 и Р2Р, то и Р1Р.

Определение 2: Задача является NP-трудной, если каждая задача,

входящая в NP, преобразуется в нее. Задача является NP-полной, если она

является одновременно NP-трудной и принадлежит NP.

31

Преобразо-

вание за

t Nm

Алгоритм

решения Р2

Преобразо-

вание за

t Nm

Вход

задачи

Р1

Вход

задачи

Р2

Выход

задачи

Р2

Выход

задачи

Р1