1.2. Оценка сложности алгоритмов

Алгоритму решения задачи предъявляются два противоречивых требования:

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

- быть эффективным в смысле затрат времени и памяти ЭВМ.

Несмотря на то, что объемы памяти и быстродействие ЭВМ выросли колоссально, такой подход к оценке эффективности продолжает оставаться справедливым.

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

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

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

При анализе с задачей связывается некоторое число, называемое размером задачи, которое выражает меру количества (объема) исходных данных. В качестве размера могут выступать размеры массивов, число вершин или дуг графа, число записей в файле и т.п. время выполнения программы T(n) зависит от размера n, единица измерения T(n) не определена. Традиционно определяют время выполнения T(n) в наихудшем случае как меру сложности алгоритма.

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

Если алгоритм А имеет время выполнения T_A(n)=cn², а алгоритм B – T_B(n)=kd², где c, d, k – константы, то в зависимости от их соотношения может оказаться, что для малых n более эффективным является алгоритм В, в то же время очевидно, что для больших n более эффективным будет алгоритм А. это связано с тем, что функции T_A(n) и T_В(n) имеют различные скорости роста.

Для описания скорости роста функции используется О-символика. Так, T(n)=О(n²) означает, что время выполнения программы T(n) имеет порядок О(n²) и подразумевается, что существуют положительные константы с и n₀, такие, что для всех n≥n₀, выполняется неравенство T(n)≤cn². Аналогично T(n) имеет порядок О(f(n)), если существуют константы с и n₀, такие, что для всех n=n₀ выполняется неравенство T(n)≤cf(n), тогда f(n) определяет степень роста. Говорят, что f(n) является верхней границей сложной задачи. Если мы пытаемся улучшить алгоритм с целью снизить время выполнения задачи, то возникает вопрос, где необходимо остановиться, т.к.дальнейшее улучшение невозможно, т.е. найти нижнюю границу сложности алгоритма. Определение нижней границы вызывает существенные затруднения и потому редко выполняются.

Определим сложность алгоритма сортировки методом пузырь­ка массива А с nэлементами. Основу алгоритма составляет двойной цикл.

for (i=0; i<n-1, i++)

for(j=n-1; j<i; j - -)

if (A[j]<A[j-1])

<перестановка элементов A[j] и A[j-1]>

Перестановка элементов требует фиксированного времени. Для каждого i, устанавливаемого внешним циклом поi, внутрен­ний цикл по j выполняется (n-i) раз, общее количество шагов оп­ределяется суммой

(n-i)=(n²-n)/2.

Следовательно, в худшем случае количество перестановок рав­но этому же значению. Таким образом, алгоритм метода пузырь­ка имеет временную сложность О(n²), если даже в некоторых ша­гах (или даже всех) перестановок элементов не будет.

Если при некотором j не будет ни одной перестановки, то это означает, что массив уже отсортирован и процесс сортировки можно прекратить. Для этого достаточно ввести управляющий переключатель p, который устанавливается в нуль в начале внеш­него цикла. Если во внутреннем цикле перестановок не было, его значение не изменяется, и по этому признаку осуществляется вы­ход из внешнего цикла. Очевидно, что временная сложность бу­дет равна О(1), если исходный массив был отсортирован, и О(n²) – в худшем случае, когда массив был отсортирован в об­ратном порядке.

При вычислениях времени выполнения программ с примене­нием O-символики пользуются правилами сумм и произведений. Правило сумм заключается в следующем. Пусть время выполне­ния двух фрагментов программы Т₁(n) и Т₂ (n) имеет порядок 0(f₁(n}) и T(f₂(n)) соответственно. Время последовательного вы­полнения этих фрагментов вычисляется как Т₁(n}+Т₂(n) = O(f₁(n)) + O(f₂(n)) и имеет порядок O(max(f₁(n),f₂(n))). По правилу произведений: Т₁(n) • Т₂(n) = O(f₁(n) • f₂(n)). Тогда с применением этих правил можно определить время выполнения операторов базовых структур программ.

1. Время выполнения последовательности операторов опре­деляется по правилу сумм, т.е. равно наибольшему времени вы­полнения одного оператора в данной последовательности.

2. Время выполнения оператора ветвления определяется наи­большим временем выполнения одной из ветвей оператора.

3. Время выполнения цикла определяется как произведение вре­мени: выполнения тела цикла на количество повторений цикла.

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

Пусть теперь для любого состояния алгоритма возможно иметь более одного следующего. Когда детерминированный алгоритм доходит до того места, где требуется выбрать одну из альтерна­тив, он исследует их последовательно друг за другом и выбирает один-единственный. Недетерминированный алгоритм просматри­вает все альтернативы не последовательно, а все их одновремен­но, копируя самого себя. Эти копии, в свою очередь, могут по­рождать новые копии и т.д. Все копии продолжают выполняться все вместе до тех пор, пока одна или несколько из них не найдут решения, после этого останавливаются все копии.

Все задачи, которые могут быть решены с помощью детерминированного алгоритма за полиномиальное время, образуют один класс, класс Р-задач (от англ. Polinomial), и считаются легко разрешимыми.

Задача, сложность которой не менее fⁿ (где f — константа, или полином от n), считается экспоненциальной и относится к классу Е. При небольших значениях n экспоненциальный ал­горитм, как отмечалось выше, может быть более «быстрым», чем полиномиальный. Но различие между этими алгоритмами при больших значениях n проявляется всегда.

Есть задачи, которые не попадают ни в класс Р, ни в класс Е. В настоящее время для этих задач не найдено полиномиального алгоритма. Доказано, что они являются взаимно эквивалентными. Это означает, что если бы для одной из них удалось найти полиномиальное реше­ние, то все они также получили бы полиномиальное решение.

Задачи, которые могут быть решены с помощью недетермини­рованного алгоритма за полиномиальное время, относятся к классу NP-задач (NondeterministicallyPolinomial). Очевидно, что PNP,т.е. каждая задача, разрешимая по детерминированному алгорит­му за полиномиальное время, также разрешима за полиномиаль­ное время по недетерминированному алгоритму. Истинность обратного утверждения не доказана. Она является одним из не разрешенных вопросов современной математики и информатики.

Определение 1. Задача Q сводится к задаче R тогда и только тогда, когда для всякого решения s задачи R существует функция g(s), которую можно вычислить полиномиально и которая является решением задачи Q (QR). Это означает, что если мы умеем решать задачу R, то мы умеем решать и задачу Q.

Определение 2. Если одновременно QR и RQ, то го­ворят, что Q и R эквивалентны.

Определение 3. Задача называется NP-сложной (NP-трудной) тогда и только тогда, когда к ней сводима любая задача из класса NP Сама NP-сложная задача может принадлежать как к классу Р, так и к классу NP.

Определение 4. Задача называется NP-полной в том и только в том случае, если она является NP-сложной и попадает в класс NP.

Задача разрешимости логического выражения заключается в следующем. Пусть дано выражение Е, которое включает логичес­кие операторы ИЛИ, И, НЕ и логические переменные q₁, q₂, ...,q_n.Нужно найти такие значения переменных q_i, чтобы при этих значениях выражение E(q₁, q₂, ...,q_n) былоистинным. Эта задача по­падает в класс NP.

В 1971 г. Куком была доказана теорема: задача разрешимости логического выражения является NP-сложной.

Так как задача разрешимости принадлежит к классу NP, то она является NP-полной.

Данная теорема утверждает, что решение любой задачи из класса NP может быть получено из решения задачи разрешимости путем некоторой трансформации, которая тоже полиноми­альна. Иначе, для решения произвольной задачи класса NP достаточно уметь решать задачу разрешимости. Трудность заклю­чается в том, что мы не умеем как следует решать задачу разре­шимости.

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