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

Глава 2. Сложность алгоритмов.
2.1 Время и вычислительная сложность алгоритмов.
Временная сложность алгоритма(T(N) , где N — размер задачи) — время выполнения алгоритма, измеряемое в шагах (инструкциях алгоритма, которые необходимо выполнить для достижения результата). То есть количество элементарных операций, составляющих алгоритм решения этой задачи (:=,<>, =, +, -, *, /; и, или, не, хор; вызов, возврат).
Различают три типа временной сложности в зависимости от сочетания входных данных (эквивалентность, разреженность, порядок и другие свойства входных данных) при решении задачи.
https://pandia.ru/text/78/183/images/image002_151.gif "ширина="178 высота=60" высота="60">
Оказывается, что T(N)=C* справедливо для квадратной матрицы N2.
При этом элементарные операции представляют собой комбинацию «+» и «*».
Если исходная матрица тождественна, мы получаем лучший случай.
Если половина элементов в матрице равна 0, а половина равна 1, мы получаем среднее состояние.
Константа WITH, которую нельзя точно выразить, описывает влияние внешних факторов на время выполнения алгоритмов (скорость компьютера, скорость компиляции). Поэтому не совсем корректно использовать единицы времени для оценки временной сложности алгоритмов. В этом случае говорят, что временная сложность алгоритма умножения матрицы на вектор пропорциональна . N2.
2.2 Ова Ω - знаки.
В возрастающем характере поведения временной сложности N (N® ¥ ) называется асимптотической сложностью алгоритма.
Для описания скорости роста асимптотической сложности мы используем O-нотацию. С точки зрения временной сложности алгоритма N2 :
Т(N)= О(N2)= О(f(N)),
Тогда предполагается, что существуют положительные константы C, n0 =const (C>0), такие, что неравенство N ³ N0 выполняется для всех
Т(N) £ С* f(N)
Это верхний предел оценки сложности.
Пример 2:
Пусть T (0) = 1, T (1) = 4, ..., T (N)=(N+1) 2, тогда временная сложность этого алгоритма находится в порядке возрастания T(N)= O( N2 ).
Можно показать, что для всех N > n0 n0 = 1, C = 4 выполняется неравенство (1).
(N+1)2 £ 4* N2
Пример 3:
Если временная сложность записана в виде полинома
T(N)= C1 N2 + C2 N + C3 ,
то такой алгоритм имеет порядок сложности, кратный степени максимального элемента полинома, так как растет быстрее всего. N® ¥ :
Т(N)=О(N2).
Например:
3 n2 +5 n+1 £ 5 n2
"н³ 1
Пример 4:
Если некоторый алгоритм имеет кратную сложность 3 n, то можно показать, что порядок возрастания скорости не может быть мультипликативным O(2 n):
T(N)=3 n¹ O(2 n).
Пусть C, n0 — константы, так что выполняется следующее неравенство:
3н£ С*2 п, п > п0 .
Отсюда получаем:
С³ (3/2)2, н> п0.
Но при n® ¥ не существует такой константы С, удовлетворяющей этому неравенству.
Помимо верхнего предела сложности, существует еще и нижний предел скорости роста временной сложности:
Т (N) ³ V (f (N))
Из неравенства (2) следует, что существует некоторая постоянная С временная сложность N® ¥ для этого
В зависимости от значения константы скорость роста сложности алгоритма БИЛАН может существенно различаться.
Пример 5:
Пусть временная сложность записывается формулой
Т (Н) = 3n2 –100n + 6 = О (n2)
3n2 > 3n2 –100n + 6, n³ 1, C = 3.
Если С1 > 0 (С1 = 0,00001), то выполняется неравенство
10-5 п2 > 3 п2 –100 п+6, п³ 1
не выполнено.
Но порядок возрастания сложности можно показать
3н2 –100н + 6¹ О (Н).
С * N< 3N2, N>С.
3n2 –100n + 6 = (n2)
С=2,29, н³ n0.
2,99* n2 < 3 n2 –100 n+6