Глава 2. Сложность алгоритмов.

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

Временная сложность алгоритма (T(N), где N – размер задачи) – это время выполнения алгоритма, измеренное в шагах (инструкциях алгоритма, которые нужно выполнять для достижения результата). Т. е. это – число элементарных операций, из которых складывается алгоритм решения задачи (:=, <>, =, +, –, *, /; and, or, not, xor; call, return).

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

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

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

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

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

Пример 1:

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

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

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

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

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

Константа С, которая не может быть точно выражена, характеризует влияние внешних факторов на время выполнения алгоритмов (быстродействие ЭВМ, скорость компиляции). Поэтому использование единиц времени для оценки временной сложности алгоритмов не совсем корректно. В этом случае говорят, что временная сложность алгоритма умножения матрицы на вектор пропорциональна N2.

НЕ нашли? Не то? Что вы ищете?

2.2 O и Ω – нотации.

Характер поведения временной сложности при увеличении N (N®¥) называется асимптотической сложностью алгоритма.

Для описания скорости роста асимптотической сложности используется О-нотация. Когда говорят, что временная сложность алгоритма имеет порядок N2:

T(N)=O(N2)=O(f(N)),

То подразумевается, что существуют положительные константы C, n0=const (C>0), такие, что для всех N ³ N0 выполняется неравенство

T(N) £ C*f(N)

(1)

Это – верхняя граница оценки сложности.

Пример 2:

Пусть Т(0)=1, Т(1)=4, …, Т(N)=(N+1)­­­­2, тогда временная сложность этого алгоритма имеет порядок роста T(N)=O(N2).

Можно показать, что для всех N > n0 при n0 = 1, C = 4 выполняется неравенство (1).

(N+1)2 £ 4*N2

Пример 3:

Если временная сложность записывается в виде полинома

T(N)=C1N2+C2N+C3,

то такой алгоритм имеет порядок сложности, кратный степени максимального элемента полинома, т. к. он растет наиболее быстро при N®¥:

T(N)=O(N2).

Например:

3n2+5n+1 £ 5n2

" n ³ 1

Пример 4:

Если некоторый алгоритм имеет сложность, кратную 3n, тогда можно показать, что порядок роста скорости не может быть кратен O(2n):

T(N)=3n¹ O(2n).

Пусть существуют константы C, n0, такие, что выполняются неравенство:

3­­­­­n £ C*2n, n > n0.

Отсюда получаем:

С ³ (3/2)2, n > n0.

Но при n®¥ не существует такой константы С, которая удовлетворяла бы данному неравенству.

Кроме верхней границы сложности существует и нижняя граница скорости роста временной сложности:

T(N) ³ W(f(N))

(2)

Неравенство (2) подразумевает, что существует некоторая константа С, для которой при N®¥ временная сложность

T(N) ³ C*f(N).

Учитывая сложность точного определения T(N) (асимптотической временной сложности), в зависимости от размеров исходных данных на практике используют нижние и верхние границы временной сложности алгоритма:

W
 

T(N) =q (f(N))

В зависимости от значения константы С скорость роста сложности алгоритма может существенно меняться.

Пример 5:

Пусть временная сложность записывается формулой

T(N)=3n2 –100n+6=O(n2)

3n2 >3n2 –100n+6, n³1, C=3.

Если С1»0 (С1=0,00001), тогда неравенство

10-5n2 > 3n2 –100n+6, n³1

не выполняется.

Но можно показать, что порядок роста сложности

3n2 –100n+6 ¹ O(N).

C*N < 3N2, N>C.

3n2 –100n+6=(n2)

C=2.29, n ³ n0.

2.99*n2 < 3n2 –100n+6

Можно показать, что нижняя граница

3n2 –100n+6 ¹ W(n3) при С=1.

Неравенство 3n2 –100n+6 ³ n3 не выполняется.

3n2 –100n+6=W(n)

C1= , n>n0.

C1n 3n2-100n+6 (верхняя граница)

C1n ³ 3n2-100n+6 (нижняя граница)

Учитывая сложность оценки, считают, что предпочтительнее являются алгоритмы, имеющие меньший порядок роста. Т. е. если одну и ту же задачу можно решить двумя алгоритмами, для которых порядок сложности кратен O(N2) и O(N3) соответственно, то более эффективным при ®¥ будет первый алгоритм.

Однако, если учитывать константы С1 и С2 при анализе границ, то в некоторых случаях второй алгоритм будет более эффективным.

Например:

f1(N)=100n2

f2(N)=5n3

n0=20 – критическая точка.

Другой причиной предпочтения алгоритмов с меньшим порядком сложности является то, что чем меньше порядок сложности, тем больший размер задачи N можно решить практически.

Вывод: следует создавать алгоритмы, для которых порядок сложности кратен N или logN : O(N), O(logN), O(MlogN).

Алгоритмы, порядок сложности которых кратен O(2n), O(an) дают экспоненциальный рост сложности.

ПРИМЕР: Проведём анализ временной сложности нескольких алгоритмов решения одной и той же задачи, для которых известны функции скорости роста сложности.

Таблица Скорости роста сложности для различных алгоритмов.

N

ln(N)

N

n*lg(N)

n2

2n

n!

10

3 нс

10 нс

33 нс

100 нс

1 мкс

3,63 мс

20

4 нс

20 нс

86 нс

400 нс

1 мс

77 лет

50

2,5 мкс

13 дней

100

4*1013 лет

105

0,13 мс

100 мс

106

10 с

107

16,7 мин

109

30 мс

1 с

29,9 с

31,7 лет

Пример 6:

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

В этом случае алгоритм с быстро растущей сложностью может оказаться предпочтительнее для решения задач с малыми размерами данных (n®0).

Пусть заданы пять алгоритмов решения одной и той же задачи, имеющие сложности:

А1: 100N

А2: 100N*logN

А3: 10N2

А4: N3

А5: 2N

Тогда для задач с N=2¸9 более быстродействующим будет А5 (f(N) ~ 4¸512). Другие алгоритмы при подстановке дадут существенно более низкие показатели.

При N=10¸58 предпочтительным оказывается А3.

При N=59¸1024 самым эффективным будет А2.

При N>1024 предпочтителен А1.

Для программ, состоящих из нескольких последовательно или параллельно выполняющихся алгоритмов, сложность оценивается по правилу сумм и правилу произведений.

Правило сумм: Пусть программа состоит из двух последовательно выполняющихся алгоритмов Р1 и Р2, для которых определены сложности O(f(n)) и O(g(n)) соответственно. Тогда временная сложность всей программы будет определяться как сумма временных сложностей каждого из алгоритмов:

T(n) = T1(n)+T2(n)

В общем случае получаем:

T(n) Þ O(max f(n), g(n))

Правило произведений: Пусть временная сложность программы, состоящей из двух параллельно выполняющихся алгоритмов, имеющих порядок сложности O(f(n)) и O(g(n)) соответственно, определяется как произведение временных сложностей каждого из алгоритмов:

T(n) = T1(n)*T2(n)

В общем случае:

T(n) Þ O( f(n)*g(n))

Логарифмы.

2.3. Рекурсия.

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

f(n) Þ f(n* f(n-1))

Например, для рекурсивного вычисления алгоритма n! Сложность будет зависеть от сложности каждого из алгоритмов, входящих в рекурсию.

В общем случае T(n) ~ O(N).

Другие рекурсивные алгоритмы в общем случае имеют временную сложность T(n) ~ O(an), где a=const, что в результате дает суммарную сложность, большую, чем сложность не рекурсивного алгоритма решения этой же задачи.

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

2.4.2 Алгоритмы восстановления зависимостей.

В ряде случаев неизвестна структура программы, и можно лишь определить время ее работы при различных размерах входных данных T(N) (сек.)

Для построения аналитической зависимости сложности программы оценивают функцию T(N) на некотором интервале [Nmin, Nmax]. Затем проводят аппроксимацию найденной кривой некоторой аналитической функции с изменением параметров функции и оценкой ошибки аппроксимации.

Как правило, в качестве такой функции используют известные функции временной сложности: O(n!), O(XN), O(NX), O(logN), O().

Этого достаточно для приближенной оценки сложности.

Если известны несколько функций аппроксимации, дающие примерно одинаковую точность, то выбирают ту из них, которая имеет минимальную сложность в качестве W(N), а с максимальной сложностью – в качестве O(N).

Пример 1:

В результате эксперимента над программой была получена таблица временных сложностей:

N

T1, сек.

T2, сек.

100

~ 0,1

~ 0,1

200

1,5

2,3

500

3,9

5,9

1000

7,6

11,9

5000

31

6,1

10000

68

173

20000

147

472

В результате поиска аппроксимации функции была получена следующая аналитическая зависимость:

Пример 2:

Часто бывает, что на время работы одного и того же алгоритма кроме размера задачи влияют другие параметры, вводимые пользователем.

В этом случае строят семейство функций аппроксимации и находят аналитически сложность алгоритма.

N

a=5

a=10

a=15

25

8

2

1

50

32

4

2

75

88

7

3

100

250

10

4

125

720

13

5,5

150

200

18

7

175

5400

23

8,5

200

15000

30

10

2.4 Классы P - (polynomial) и NP - (nondeterminated polynomial) задач.

2.5.1 Понятие Р - и 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)

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

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

В недетерминированном алгоритме (НДА) для любого данного состояния может быть больше одного допустимого следующего состояния, т. е. такой алгоритм в каждый момент времени может выполнить больше одного оператора.

НДА не является случайным или вероятностным алгоритмом. Он представляет собой алгоритм, который может находиться во многих состояниях (это эквивалентно параллельному решению задачи с множеством вариантов).

Пример:

 

Детерминированный алгоритм (ДА) решал бы эту задачу последовательно (перебор всех вариантов, сравнение с критерием оптимальности K0 до тех пор, пока не выберет альтернативу А0).

НДА может одновременно (параллельно) получить все альтернативы и сравнить с K0, копируя самого себя в виде отдельного процесса для каждой альтернативы, которая выполняется независимо.

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

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

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

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

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

Очевидно, что никакое физическое устройство не способно на неограниченное недетерминированное поведение, значит, НДА является теоретическим методом.

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

2.5.2 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.

2.5.3 Примеры задач NP-класса.

Задача о выполнимости.

Пусть х1, х2, …, хn – множество логических переменных; – их отрицания или дополнения.

if xi = true then = false

Ú - И; Ù - ИЛИ.

Дизъюнкция: х1 Ú х5 Ú Ú…

Конъюнкция: х4 Ù х3 Ù Ù…

Конъюнктивная нормальная форма:

E*(x1, …, xn) = (x1 Ú x2 Ú x3) Ù (x1 Ú Ú ) Ù ( Ú x4) Ù ( ) (*)

Задача о выполнимости заключается в определении, является ли булевская функция, записанная в КНФ, выполнимой.

Любая булевская функция может быть представлена в КНФ по правилу Де Моргана:

АÚ(ВÙС)=( АÚВ)Ù(АÚС)

Говорят, что булевская функция выполнима, если существует некоторое присваивание переменным true или false, при этом функция должна быть равна true.

Для функции (*) она будет выполнима, если ввести следующие присваивания:

(*)

Например:

Функция

f2(xi)=(x1 Ú x2)Ù( )Ù()

не является выполнимой, т. к. при любых xi f2(xi)=false.

Теорема:

Задача о выполнимости является NP-полной.

for i=1 to N do

xi выбор (true, false)

if E(x1, x2, …, xN) then успех

else неудача

Используя преобразование задачи Р1 в Р2, можно показать, что даже ограниченный случай задачи о выполнимости является NP-полным.

К-выполнимость.

К-выполнимость означает, что любой дизъюнкт, входящий в КНФ, содержит не более К логических переменных.

Минимальный случай К=3. Для булевской функции, представленной в КНФ, за полиномиальное время можно найти функцию Е*(х2), содержащую не более трех переменных в каждом дизъюнкте. Тогда Е выполнима, если выполнима Е*.

E*(x1, x2,…, xn)®E*(xi)

Для этого используется метод уменьшения порядка дизъюнкта

(a1 Ú a2 Ú…Ú ak)=(a1 Ú a2 Ú z) Ù (a3 Ú a4 Ú…Ú ak Ú )

Применяя итерационный процесс разложения, можно получить Е*.

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

Частный случай: при К=2 функция Е входит в Р.

Примерами задач NP-класса могут послужить также задачи на графах:

1)  Определение максимума клик неориентированного графа (NP-трудная задача).

2)  Задача определения полного подграфа (NP-полная задача).

3)  Определение вершинного покрытия мощности L для неориентированного графа (NP-полная задача).

4)  Определение максимума вершинных покрытий неориентированного графа (NP-трудная задача).

5)  Задача определения существования Гамильтонова цикла для графа (NP-полная задача).

6)  Задача коммивояжера: определение оптимального движения по графу с единым вхождением в каждую вершину (NP-трудная задача).

7)  Задача составления расписания (NP-полная задача).

2.6 Алгоритмически неразрешимые проблемы

Разделяют проблемы одиночные и массовые.

Например:

5+7=? – одиночная проблема.

х+у=? – массовая проблема.

Принципиально неразрешимыми должны быть алгоритмы получения объектов, которые парадоксальны, или решения задач, из которых вытекало бы существование парадоксальных объектов.

Например, парадоксами являются:

1) 5-ая аксиома Евклида (Лобачевский дал ей опровержение).

2) 2*2=5

Пример 1:

10-ая проблема Гильберта.

Д. Гильберт в 1901 г. при решении диофантовых уравнений выдвинул проблему, которая гласит:

Найти алгоритм, определяющий некоторое целочисленное решение для произвольного диофантового уравнения

F(x, y, …)=0

Это – полином с целыми показателями степеней и целыми коэффициентами при неизвестных

anxn+an-1xn-1+…+a2x2+a1x+a0=0

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

В 1970 г. ленинградский математик Ю. Матиясевич математически доказал алгоритмическую невозможность решения диофантового уравнения в общем виде.

Пример 2:

Теорема Ферма:

Не существует таких целых чисел a, b, с, n (n>2), для которых справедливо равенство

an + bn = cn

Эта теорема была доказана для многих значений n и проверена для частных случаев, однако до сих пор не создано общее доказательство теоремы.

Пример 3:

Проблема Гольдбаха.

Х. Гольбах в 1742 г. в письме к Эйлеру сформулировал проблему:

Доказать, что каждое целое число N³6 может быть представлено в виде суммы трех простых чисел

N=a+b+c

Это значит, что нужно найти алгоритм, который позволил бы для любого целого числа N³6 найти хотя бы одно разложение на три простых слагаемых.

Частый случай решения этой проблемы предложил Эйлер: для четных N эта проблема разрешима и равносильна разложению на два простых слагаемых.

И. Виноградов в 1937 г. доказал, что для нечетных N можно найти три простых слагаемых, но для четных чисел решение не найдено до сих пор.