38012

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

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

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

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

Русский

2013-09-25

146.5 KB

28 чел.

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


 

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

83910. Оперативные доступы к почкам и мочеточникам. Доступ к почечной артерии. Операции на почке и мочеточнике. Показания, техника выполнения 54.18 KB
  Доступ к почечной артерии. Доступ позволяет подойти к мочеточнику на всём его протяжении и к общей подвздошной артерии. Доступ к почечной артерии На почечной артерии выполняют следующие оперативные вмешательства: эндартерэктомию резекцию суженного сегмента почечной артерии обходное постоянное шунтирование почечной артерии дистальнее места окклюзии с помощью сосудистых протезов. Наиболее рационально при осуществлении доступа к почечной артерии использовать срединную лапаротомию и торакофренолюмботомию.
83911. Паранефральная блокада. Показания, техника выполнения. Нефроптоз 50.22 KB
  Осложнения: повреждение паренхимы почки и введение новокаина под собственную капсулу; повреждение сосудов почки; проникновение иглы в просвет восходящей или нисходящей ободочной кишок. Нефроптоз Нефроптоз патологическая подвижность почки проявляющаяся смещением органа за пределы своего анатомического ложа. При нефроптозе IIIII степени осложненном нарушением гемодинамики уродинамики хроническим болевым синдромом пиелонефритом нефролитиазом гипертензией гидронефрозом требуется хирургическая тактика проведение нефропексии...
83912. Современные технологии в хирургии 49.88 KB
  С конца 80х годов 20 века эти операции выполняют под контролем видеомонитора. В первую очередь эндохирургия охватывает операции на органах брюшной и грудной полостей лапароскопические и торакоскопические вмешательства. Минимально инвазивная хирургия область хирургии позволяющая проводить радикальные операции с минимальным повреждением структуры здоровых тканей и минимальным нарушением их функций. К минимально инвазивной хирургии относят эндоскопические операции выполняемые через естественные физиологические отверстия удаление полипов...
83913. Основы трансплантологии 52.47 KB
  Пути преодоления peкции отторжения Подбор наиболее совместимого по антигенным свойствам донора. Подавление реакиии отторжения. Подавление реакции отторжения возможно также с помощью антилимфоцитарного глобулина который оказывает супрессивное действие на лимфоциты играющие ключевую роль в реакции отторжения. Пациенты с пересаженными органами вынуждены принимать препараты пожизненно Хирургический путь борьбы с реакцией отторжения.
83914. Известные отечественные хирурги: Шевкуненко, Оппель, Греков и другие. Их вклад в развитие хирургии 53.31 KB
  Их вклад в развитие хирургии. Автор 50 научных трудов в том числе первого отечественного капитального руководства по оперативной хирургии в трех томах и руководства по топографической анатомии. Под его редакцией вышел Краткий курс оперативной хирургии с топографической анатомией 1951 переведённый на многие иностранные языки. Греков добился благодаря своим научным работам в области абдоминальной хирургии.
83915. Известные зарубежные хирурги: Бильрот, Кохер и другие. Развитие хирургии путём совершенствования оперативной хирургии 50.61 KB
  Развитие хирургии путём совершенствования оперативной хирургии. Бильрота связан ряд важных достижений хирургии в частности: первая эзофагэктомия первая ларингэктомия и что особо значимо первая успешная гастрэктомия по поводу рака желудка. Кроме того разработал ряд хирургических инструментов применяемых в хирургии в наши дни. Им опубликованы работы посвященные вопросам клинической хирургии в том числе костному туберкулезу и другим заболеваниям костей разработаны новые методы хирургических операций артротомия по Фолькману клиновидная...
83916. Н.И. Пирогов - вклад в развитие хирургии и топографической анатомии 46.6 KB
  Пирогов вклад в развитие хирургии и топографической анатомии. Пирогов основоположник топографической анатомии. Пирогов занял место профессора госпитальной хирургической клиники Медико хирургической академии СПб где с первых же дней стал читать знаменитый курс лекций по топографической анатомии он организовал анатомический институт в котором объединил практическую описательную и патологическую анатомию. Пирогов оформил все основные положения созданной им науки топографической анатомии в монументальном труде Полный курс анатомии...
83917. В.Н. Шевкуненко – создатель современного учения топографической анатомии на основе изменчивости 50.3 KB
  Геселевичем ввёл понятие типовой анатомии человека которая исследует распределение тканевых и системных масс в организме и расположение органов и частей тела с точки зрениях их развития. Типовая анатомия отмечает крайние типы строения и положения органов наблюдаемые у людей определённого телосложения. Шевкуненко исходными побуждающими моментами к таким исследованиям были: частое несоответствие формы и положения органов видимых во время операции с нормой описываемой в руководствах; несовершенство многих хирургических доступов при...
83918. Шовные материалы. Капрон, пролен, дексон, викрил и другие 50.37 KB
  Основные требования к шовному материалу: Биосовместимость отсутствие токсического аллергенного и тератогенного влияния шовной нити на ткани организма. Прочность нити и сохранение её свойств до образования рубца. Необходимо учитывать прочность нити в узле Атравматичность зависит от структуры и вида нити её манипуляционных свойств эластичности и гибкости. Понятие атравматичности включает несколько свойств присущих шовным материалам: Поверхностные свойства нити: кручёные и плетёные нити имеют шероховатую поверхность и при прохождении...