38012

ОПРЕДЕЛЕНИЕ ЭФФЕКТИВНОСТИ И СЛОЖНОСТИ ИССЛЕДУЕМЫХ АЛГОРИТМОВ

Лабораторная работа

Информатика, кибернетика и программирование

Краткая теория Теория сложности алгоритмов Сложность алгоритма характеристика алгоритма определяющая зависимость времени выполнения программы описывающей этот алгоритм от объёма обрабатываемых данных. Формально определяется как порядок функции выражающей время работы алгоритма. Эффективность алгоритма временная сложность в самом худшем случае Ofn или просто fn.

Русский

2013-09-25

146.5 KB

20 чел.

5

Лабораторная работа № 8

«ОПРЕДЕЛЕНИЕ ЭФФЕКТИВНОСТИ И СЛОЖНОСТИ ИССЛЕДУЕМЫХ АЛГОРИТМОВ»

Цель работы: научиться вычислять эффективность и сложность исследуемого алгоритма.

Задача работы: овладеть навыками определения эффективности и сложности исследуемых алгоритмов.

Порядок работы :

  1.  изучить описание лабораторной работы;
  2.  по заданию, данному преподавателем, разработать алгоритм решения задачи;
  3.  исследовать программу, составленную на любом языке;
  4.  решить задачу;
  5.  оформить отчет.

Краткая теория

Теория сложности алгоритмов

Сложность алгоритма - характеристика алгоритма, определяющая зависимость времени выполнения программы, описывающей этот алгоритм, от объёма обрабатываемых данных. Сложность можно оценить по содержанию программы. Так, если в программе выполняется вложенный цикл с числом шагов внешнего цикла m и вложенного цикла n, то сложность будет пропорциональна mn. Формально определяется как порядок функции, выражающей время работы алгоритма.

Эффективность алгоритма – временная сложность в самом худшем случае O(f(n)) или просто f(n). Функция от n f(n) равна максимальному числу шагов, выполняемых алгоритмом и имеет порядок роста O(f(n)), причём максимум берётся по всем входным данным длины n. Существует константа c, такая, что для достаточно больших n величина cf(n) является верхней границей количества шагов, выполняемых алгоритмом для любых входных данных длины n. Анализ рекурсивных программ значительно сложнее обычных, так как зачастую требуется решать дифференциальные уравнения. Для их анализа необходимо применять методы похожие на методы решения дифференциальных уравнений. При анализе рекурсивных процедур составляются рекуррентные соотношения, которые получают исходя из структуры рекурсивного алгоритма, отражающие характер рекурсивного вызова алгоритма и зависящие от величины входных данных.

Решение рекуррентных соотношений

Существуют 3 способа решения рекуррентных соотношений:

  1.  Находится функция f(n), которая мажорирует T(n) для всех значений n, т.е. для всех n выполняется неравенство T(n)<=f(n). Иногда только лишь предположительно определяется вид функции f(n), зависящей от некоторых неопределённых параметров. Далее подбираются такие параметры, что для всех n будет выполняться T(n)<=f(n).
  2.  Последовательно подставляются в рекуррентное соотношение зависимости T(m), где m<n, так, чтобы из правой части были исключены все T(m) с m>1, оставив толь ко T(1). Но так как T(1) всегда является константой, то получится под конец зависимость от констант и n.
  3.  Использование общих решений.

Оценка решений рекуррентных соотношений

Рассмотрим пример процедуры-функции mergesort сортировки слиянием, входные данные которой – это список элементов длиной n, а выходные – это отсортированный список. Эта функция так же использует процедуру слияния merge, входные данные которой – это два отсортированных списка L1 и L2. Данная процедура просматривает эти списки поэлементно, начиная с больших. На каждом шаге наибольший элемент из двух сравниваемых удаляется из своего списка и помещается в выходные данные. Получается тем самым единый отсортированный список, содержащий все элементы L1 и L2. Процедура на списках merge, длиной n/2, выполняется за время порядка O(n).

function mergesort(L:LIST; n:integer):LIST;{L - список типа LIST длиной n, где n является степенью числа 2}

var    L1,L2:LIST;

begin

if n=1 then return(L)

else begin

разбиение L на две части L1 и L2, каждая длиной n/2;

return(merge(mergesort(L1, n/2),(mergesort(L2, n/2)));

end;

end; {mergesort}

Пусть T(n) - время выполнения процедуры mergesort в самом худшем случае. Анализируя текст программы, запишем рекуррентное неравенство, которое ограничивает сверху T(n):

                               (7.1)

В данном неравенстве c1 – это количество шагов выполняемых алгоритмом над списком L длиной 1. Время работы процедуры можно разбить на две части, если n>1. Первая часть состоит из: 1) проверки n<>1, 2) разбивки L, на две равные части и 3) вызова процедуры merge. Эти три операции требуют или фиксированное время для выполнения первой части или пропорционального n для второй и третьей. Следовательно, можно выбрать такую константу c2, которая будет создавать ограничение для выполнения данной части процедуры равное c2*n. Вторая часть процедуры mergesort состоит из двух рекурсивных вызовов этой процедуры для списков длины n/2, которые будут требовать время 2T(n/2). Так было получено второе неравенство.

Формулу верхней границы в замкнутой форме можно получить лишь, если n является степенью числа 2. При выполнении этого условия T(n) можно оценить для любых n. Другими словами, если n лежит в промежутке , то значение T(n) располагается между T(2i)…T(2i+1). Нетрудно заметить, что выражение 2T(n) можно заменить на T((n+1)/2)+T((n-1)/2) для нечётных n>1. Таким образом, можно найти решение рекуррентного соотношения в замкнутой форме для любых n. Замкнутая форма - это вид функции T(n), не включающей в себя никаких выражений T(m) для m<n.

Произведём оценку рекуррентного соотношения (7.1).

Заменим в этом соотношении n на n/2 и получим

                    (7.2)

Подставим правую часть (7. 2) в (7. 1)

(7.3)

Заменяя аналогичным образом в (7. 1) n на n/4, получаем оценку для T(n/4): T(n/4)2T(n/8)+c2*n/4. Подставим эту оценку в (7.3) и получим такое выражение:

                     (7.4)

Проанализировав характер изменения T(n) преобразуем (7.1) к виду:

                   (7.5)

Предположим, что , тогда при i=k в правой части (7.5) находится T(1):

                  (7.6)

Так как , то ,а T(1) c1, то (7.6) можно преобразовать

.                         (7.7)

Неравенство (7.7) демонстрирует верхнюю границу для T(n), а порядок роста T(n) не более O(n logn).

Задания по вариантам:

Для своего варианта – столбец A, выбрать рекуррентное уравнение и значение T(1). Необходимо решить данное рекуррентное соотношение и определить эффективность алгоритма, описанного функцией T(n).

Таблица 1

Задание на лабораторную работу №8

A

Уравнение

T(1)

A

Уравнение

T(1)

1

T(n)=3T(n/2)+n

2

18

T(n)=3T(n-1)+

9

2

T(n)=2T(n-1)+2

2

19

T(n)=3T(n/2)+n

9

3

T(n)=T(n/2)+

5

20

T(n)=3T(n-1)+9

1

4

T(n)=2T(n/2)+n

2

21

T(n)=2T(n/2)+

2

5

T(n)=T(n/2)+logn

1

22

T(n)=2T(n/2)+n

1

6

T(n)=9T(n/2)+

9

23

T(n)=T(n/2)+3logn

3

7

T(n)=2T(n/2)+5

3

24

T(n)=8T(n/2)+

2

8

T(n)=3T(n/2)+n

3

25

T(n)=T(n/2)+9

3

9

T(n)=16T(n-1)+4

3

26

T(n)=3T(n/2)+n

4

10

T(n)=T(n-1)+3n

3

27

T(n)=2T(n-1)+9

1

11

T(n)=2T(n/2)+n

8

28

T(n)=2T(n-1)+3n

6

12

T(n)=4T(n/2)+2

8

29

T(n)=2T(n/2)+n

4

13

T(n)=3T(n/2)+

3

30

T(n)=(T(n-1))2

4

14

T(n)=2T(n/2)+

4

31

T(n)=T(n/2)+2

1

15

T(n)=2T(n/2)+logn

2

32

T(n)=2T(n/2)+

16

16

T(n)=(T(n-1))2

4

33

T(n)=T(n/2)+2logn

2

17

T(n)=4T(n/2)+4

4

34

T(n)=2T(n-1)+2

2

Продолжение таблицы 1

A

Уравнение

T(1)

A

Уравнение

T(1)

35

T(n)=(T(n-1))2

9

43

T(n)=3T(n/2)+3

3

36

T(n)=T(n-1)+3n3

3

44

T(n)=3T(n/2)+n

8

37

T(n)=3T(n/2)+n

1

45

T(n)=3T(n-1)+2

10

38

T(n)=4T(n-1)+2

8

46

T(n)=2T(n-1)+2n

2

39

T(n)=2T(n/2)+3n3

1

47

T(n)=2T(n/2)+n

3

40

T(n)=2T(n/2)+n

64

48

T(n)=9T(n/2)+1

3

41

T(n)=9T(n/2)+logn

3

49

T(n)=T(n/2)+5 n3

5

42

T(n)=4T(n/2)+ n2

4

50

T(n)=6T(n/2)+ n2

8


 

А также другие работы, которые могут Вас заинтересовать

24755. Числовые составные адреса 13.82 KB
  Числовые составные адреса Каждый из множества ПК входящих в Интернет имеет свой собственный уникальный адрес. Это числовой адрес IPадрес: IP Internet Protocol IPадрес состоит из четырех групп цифр например 194. Этот адрес неудобен для человека поэтому IPадресам поставлены в соответствие символьные адреса доменные имена. Служба которая обеспечивает преобразование символьного адреса доменного имени в числовой IPадрес называется службой доменных имен DNS DomainName Service.
24756. Принципы и порядок отнесения сведений к государственной тайне. Грифы секретности носителей этих сведений 55.02 KB
  Принципы и порядок отнесения сведений к государственной тайне. Грифы секретности носителей этих сведений. Государственная тайна защищаемые государством сведения в области его военной внешнеполитической экономической разведывательной контрразведывательной и оперативнорозыскной деятельности распространение которых может нанести ущерб безопасности Российской Федерации; Носители сведений составляющих государственную тайну материальные объекты в том числе физические поля в которых сведения составляющие государственную тайну находят...
24757. Порядок допуска и доступа должностных лиц и граждан к сведениям, составляющим государственную тайну 40.55 KB
  Граждане характер деятельности которых подразумевает использование информации государственной тайны могут заниматься этой работой только после получения допуска установленной формы и в установленном порядке. Степень проверочных процедур определяется уровнем секретности информации к которой оформляемое лицо желает получить допуск. Транспортный уровеньTransport layer реализует передачу данных между двумя программами функционирующими на разных компьютерах обеспечивая при этом отсутствие потерь и дублирования информации которые могут...
24758. Правовое регулирование отношений по защите информации в информационных и телекоммуникационных сетях, а также в сети Интернет 32.84 KB
  Правовое регулирование отношений по защите информации в информационных и телекоммуникационных сетях а также в сети Интернет. Правовое обеспечение безопасности информационных и телекоммуникационных систем направлено на создание правовых условий для противодействия следующим угрозам в информационной сфере: противоправные сбор и использование информации; нарушения технологии обработки информации; внедрение в аппаратные и программные изделия компонентов реализующих функции не предусмотренные документацией на эти изделия; разработка и...
24759. Правовой порядок установления соответствия параметров объектов информатизации и средств защиты информации требованиям нормативных документов 75.83 KB
  Правовой порядок установления соответствия параметров объектов информатизации и средств защиты информации требованиям нормативных документов. Деятельность по аттестации объектов информатизации по требованиям безопасности информации осуществляет ФСТЭК России бывш. Объект информатизации совокупность информационных ресурсов средств и систем обработки информации используемых в соответствии с заданной информационной технологией средств обеспечения объекта информатизации помещений или объектов зданий сооружений технических средств в...
24761. Коммерческая тайна. Правовой порядок установления режима коммерческой тайны 42.57 KB
  Коммерческая тайна режим конфиденциальности информации позволяющий ее обладателю при существующих или возможных обстоятельствах увеличить доходы избежать неоправданных расходов сохранить положение на рынке товаров работ услуг или получить иную коммерческую выгоду; Информация составляющая коммерческую тайну секрет производства сведения любого характера производственные технические экономические организационные и другие в том числе о результатах интеллектуальной деятельности в научнотехнической сфере а также сведения о...
24762. Особенности правовой защиты интеллектуальной собственности. Виды интеллектуальной собственности. Право авторства и авторские (исключительные) права на интеллектуальную собственность 40.21 KB
  Право авторства и авторские исключительные права на интеллектуальную собственность. Такое правовое регулирование осуществляется при помощи совокупности правовых норм образующих право интеллектуальной собственности которое является подотраслью гражданского права. Использование результата интеллектуальной деятельности или средства индивидуализации способом не предусмотренным лицензионным договором либо по прекращении действия такого договора либо иным образом за пределами прав предоставленных лицензиату по договору влечет...
24763. Особенности правовой защиты персональных данных 134.5 KB
  Особенности правовой защиты персональных данных. Эти процессы стимулируют создание системы правовой защиты персональных данных. Персональные данные любая информация относящаяся к прямо или косвенно определенному или определяемому физическому лицу субъекту персональных данных;ФЗ 152 Государственный надзор за выполнением требований законодательства в области защиты ПДн распределен между тремя ведомствами: 1 Роскомнадзор основной исполнительный и надзорный орган по защите прав физических лиц чьи персональные данные обрабатываются; 2...