38012

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

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

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

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

Русский

2013-09-25

146.5 KB

21 чел.

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


 

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

83471. Інститут правонаступництва держав в міжнародному праві. Джерела міжнародного правонаступництва 35.98 KB
  Джерела міжнародного правонаступництва Для стабільності міжнародних відносин важливе значення має послідовне виконання субєктами міжнародного права укладених ними міжнародних договорів їх міжнародних зобовязань щодо території власності членства у міжнародних організаціях тощо. Інститут правонаступництва у міжнародному праві є міжгалузевим інститутом: його норми містяться в праві міжнародних договорів праві міжнародних організацій міжнародному економічному праві та ін. Тривалий час основу інституту правонаступництва складали звичаєві...
83472. Поняття правонаступництва в міжнародному праві. Види і форми правонаступництва. Підстави правонаступництва 37.07 KB
  Види і форми правонаступництва. Підстави правонаступництва. Таким чином правонаступництво являє собою правовідносини у яких беруть участь дві сторони: державапопередниця яка була змінена іншою державою в процесі правонаступництва; державаспадкоємниця яка замінила іншу державу в процесі правонаступництва.
83473. Міжнародне правонаступництво держав щодо міжнародних договорів 38.6 KB
  Відносно усних договорів і договорів між державами й іншими субєктами міжнародного права діють звичаєві норми міжнародного права. встановлює наступні правила правонаступництва щодо міжнародних договорів: а у разі створення в результаті деколонізації нової незалежної держави діє принцип tbul rs чистої дошки: нова держава не звязана договорами укладеними колишніми державамиметрополіями і не зобовязана зберігати чинність будьякого договору або ставати його учасницею в силу виключно того факту...
83474. Міжнародно-правове регулювання правонаступництва держав відносно міжнародних договорів, державної власності, державних архівів та боргів 37.84 KB
  Однією з найважливіших проблем правонаступництва щодо державної власності є проблема компенсації за власність що переходить до державинаступниці. передбачається що в принципі такий перехід власності повинен відбуватися без компенсації якщо інше не узгоджено зацікавленими державам або не передано на вирішення відповідного міжнародного органу Державапопередниця зобовязана вжити всі заходи для запобігання пошкодження або знищення власності що переходить до державинаступниці. Правонаступництво не стосується власності яка знаходиться на...
83475. Правонаступництво України в зв’язку з розпадом СРСР 39.9 KB
  Правонаступництво України щодо Союзу PCP регулюється комплексом домовленостей з питань правонаступництва що були досягнуті між країнами які увійшли після розпаду СРСР у Співдружність Незалежних Держав серед них: Меморандум про взаємопорозуміння з питань правонаступництва щодо договорів колишнього Союзу PCP що становлять взаємний інтерес 1992 p. Україна є правонаступницею прав і обовязків СРСР які не суперечать Конституції України. було закріплено що кожна держава СНД має право підтвердити чинність для себе міжнародних договорів СРСР.
83476. Поняття і види територій в міжнародному праві 35.51 KB
  За правовим режимом територія поділяється на три основні види: 1 державна територія; 2 міжнародна територія; 3 територія із змішаним режимом. Державна територія це частина простору земної кулі що знаходиться під суверенітетом держави яка здійснює відносно неї і в її межах своє територіальне верховенство. Територія із змішаним режимом територія на якій одночасно діють норми міжнародного та національного права. До територій зі змішаним режимом також відноситься державна територія міжнародного користування що включає міжнародні річки...
83477. Демілітаризовані і нейтралізовані території 36.41 KB
  Демілітаризована територія - це територія, відносно якої держава прийняли міжнародне зобовязання скоротити або взагалі не розташовувати в її межах військові укріплення і споруди, певні види озброєнь збройних сил. Такі території створюються на основі міжнародних угод з метою забезпечення міжнародної безпеки.
83478. Поняття та склад державної території 35.77 KB
  До складу державної території входять: сухопутна територія поверхня суші включаючи острови; водна територія акваторія що включає внутрішні води і територіальне море; земні надра; повітряний простір розташований над вищевказаними просторами. До внутрішніх вод відносяться: води портів; води заток бухт лиманів ширина входу в які не перевищує 24 морські милі; води заток бухт лиманів і проток ширина входу в які перевищує 24 морські милі але які історично належать даній державі; води річок озер і інших водоймищ що...