Algoritmi i kompleksnost PDF

Алгоритми и комплексност Д-р. Томи Бошковски [email protected]  1 Сложеност на алгоритми 2 Податочни структури 3 Аретипи на алгоритми Содржина 4 Алгоритми за сортирање 5 Дрва и графови 6 Алгоритми за дрва...

Алгоритми и комплексност Д-р. Томи Бошковски [email protected]  1 Сложеност на алгоритми 2 Податочни структури 3 Аретипи на алгоритми Содржина 4 Алгоритми за сортирање 5 Дрва и графови 6 Алгоритми за дрва и графови  1 Лабораториски вежби – 20% Total Points Grade 0 – 50% 5 2 Домашни/Проекти – 20% 51% – 60% 6 Оценувње 61% - 70% 7 3 Финален испит – 60% 71% - 80% 8 81% - 90% 9 Активност на часови - 4 91% – 100% 10 дополнителни 10% Литература The Algorithm Design Manual Steven S. Skiena 2008 Introduction to Algorithms, 3rd Edition (The MIT Press) Cormen, Leiserson, Rivest, Stein 2009 Сложеност на алгоритми Алгоритми и комплекснот Д-р. Томи Бошковски Алгоритми Пред да се започне со пишување на програмскиот код на некој проблем што се решава, треба да се смисли решението на проблемот - алгоритмот Влезни Излезни податоци податоци алгоритам Алгоритми q Aлгоритам § Процедура за решавање даден q Нотации за опис на алгоритмите проблем § Говорен јазик § се одвива чекор-по-чекор § Псевдојазик § Конечен број чекори § Програмски јазик Влез Алгоритам Излез Процедура од конечен број чекори за решавање на даден проблем Какви треба да бидат Коректни алгоритмите? Ефикасни Лесни за имплементација  Податочни структури Информациите кои треба да бидат процесирани од страна на програмата се чуваат во податочни структури - data structures Од изборот на податочните структури зависи ефикасноста на алгоритмите Акции кои се изведуваат врз податочните структури: Пребарување и пронаоѓање Пример: Пребројување наоѓање телефонски број за позната Вметнување адреса и наоѓање на адреса за Сортирање познат телефонски број Бришење  Перформанси на алгоритмите За да се подобрат перформансите на алгоритмот треба да се напише добар, а потоа по можност и подобар алгоритам (оптимизација) Како се споредуваат алгоритмите? Еден проблем може да се реши на неколку начини Различни алгоритми НО, ØКако да се процени нивната ефикасност? ØКако да се споредат? Пример Споредба на два алгоритми за сортирање: 4 3 Aлгоритам A Aлгоритам B t (ms) 2 1 0 10 20 30 40 Број на податоци за сортирање, n Алгоритамот B е побрз од алгоритмот A. Еве како се споредуваат алгоритми! Споредба на алгоритми се прави преку модел кој е независен од хардверот Хипотетички компјутер - Random Access Machine Перформанси на алгоритмите Random Access Machine Секоја едноставна операција (+, *, -, =, if, call) се извршува во една временска единица Циклусите (јамките), процедурите и функциите се извршуваат во онолку временски единици колку што содржат итерации Постои неограничена меморија Броење чекори def suma( x, n): Број на извршени операции sum = 0 1 for i in range(0,n+1): n+1 sum = sum+x*x (n+1)(1+1+1)=3n+3 return sum 1 Вкупно: T(n) = 4n+6 2 T(n) е функција што го дава бројот на извршени операции во зависност бројот на влезните податоци А споредувањето? Да разгледаме 2 алгоритми, A и B, коишто решаваат ист проблем. Сме направиле анализа за потребниот број чекори за секој од алгоритмите TA (n) и TB(n) n e мерка за големината на проблемот n e број на влезни податоци Значи останува само да се споредат двете функции TA(n) и TB(n) и ќе одредиме кој е победникот! НО! Може да провериме за некоја конечна вредност за n (n0) кој алгоритам е побрз (помал број на операции) Во општ случај не знаеме колку може да биде n. 10, 100,..100 000…1 000 000 ?? Може да се покаже дека ако TA (n) =0, тогаш Алгоритамот А е побрз, подобар! СЕПАК, Не го знаеме n однапред !! ЗАТОА – ќе го разгледаме поставување горна асимптотска граница за многу големи проблемски величини За големо n Исто така... Пресметувањето на Т(n) e исцрпувачко за алгоритми со голем број инструкции и операции Не е потребно да се знае точниот број операции за да се одреди сложеноста на даден алгоритам за да се одреди кој алгоритам е поефикасен (побрз) Ни треба оценувач (функција) што ќе биде горна асимптотска граница на T(n)  Дефиниција на “Големо О” Најчесто користениот метод и нотација за проценка на сложеност на алгоритам e Големо O (Big O) Големо O е асимптотско време на извршување (број на операции) на даден алгоритам Ни треба одговор на прашањето: Како расте времето на извршување на алгоритмот како функција од бројот на влезни податоци? Големо O е горна граница Математичка алатка Крие голем број непотребни детали со придружување на едноставна проценка (функција) кон даден алгоритам Дефиниција на “Големо О” Т(n) Т(n) Формална дефиниција на ”Големо О” T(n) е O( g(n) ) ако постојат позитивни константи c и n0 такви што T(n) < c g(n) за n > n0 n е бројот на влезните податоци T(n) е функција која го опишува вистинското време на извршување на алгоритамот (број на извршени операции – една операција се изведува во една временска единица) g(n) е функција што ја карактеризира горната граница на T(n) (асимптотска граница на T(n)) најблиску е до Т(n), а секогаш е над неа, за било кое n, почнувајќи од некое n0 гарантирано е дека Т(n) не може да биде поголемо од g(n) за било кое n > n0 Како се одредува О(g(n))? Може уште повеќе да се олесни проценувањето за сложеноста на алгоритмите О(g(n)) - се зема САМО членот со најголемиот степен на асимптотската функција g(n) Правила за користење на ознаката О(..) Се отстрануваат сите членови, освен членот со највисок степен Пример O(n + n log n + n) ® O(n ) 2 2 g(n)= 𝑛! + 𝑛 𝑙𝑜𝑔𝑛 + 𝑛 Се отстрануваат константите Пример O(3n 2 ) ® O(n 2 ) O(1024) ® O(1)  Споредба на алгоритми Според RAM моделот имаме: Најдобро време на извршување Средно време на извршување Најлошо време на извршување на алгоритмот Големо О Пример: Да се напише програмски код во Python за реализација на сумата ∑)&'( 𝑖 *  Споредба на алгоритми def sum (n): Т(n)= 5n + 2 partial_sum = 0; 1 for i in range(1, n+1) n partial_sum += i*i*i; n+n+n+n = 4n return partial_sum; 1 Декларациите не влијаат на времето на извршување Се нарекува КОМПЛЕКСНОСТ на алгоритамот O(n) Правила при споредба на алгоритми Циклуси: Сума на времињата потребни да се извршат операциите во циклусот помножено со бројот на итерации for i in range(0,n) 2n O(n) a += i; b *=i; Правила при споредба на алгоритми Вгнездени циклуси: Сума на времињата потребни да се извршат операциите во циклусот помножено со производот на бројот на итерации на циклусите for i in range(0,n): n*n O(n2) for j in range(0,n): b *=i Правила при споредба на алгоритми Последователни времиња: Кај последователни извршувања се зема најголемата кардиналност од блоковите на последователни кодови for i in range(0,n): n O(n) O(n2) a[i] = 0 for i in range(0,n): for j in range(0,n): n*n O(n2) a[i] += a[j]+i+j; Комплексноста на алгоритамот е O(n2)  Правила при споредба на алгоритми IF / ELSE: Збир од времетраењето на условот и подолгото време од времетраењата на блоковите S1 и S2 if (condition): S1 else: S2  Правила при споредба на алгоритми Рекурзии: Комплексноста на рекурзијата се разгледува од случај до случај и нема генерален шаблон за нејзиното времетраење def factorial (n): if n 1): Комплексноста на n = n / 2; алгоритмот е O(log n) total+=1; return total; log2 8 = ? Одговор: 3 Принципи на споредба Низ следниот пример, решен со 3 различни алгоритми ќе се прикаже практичниот начин на проценка на нивната сложеност Пример: Да се најде најголемата позитивна подсума во низа од n цели броеви Влез: -2, 11, -4, 13, -5, -2 20 Примерот за најголемата позитивна подсума решен со три вгнездени циклуси def max_subsequence_sum(a): max_sum = 0; best_i, best_j = -1,-1 n = len(a) for i in range(0,n): n for j in range(i, n): n-i+1 this_sum=0 for k in range(i, j+1): this_sum += a[k]; j-i+1 if this_sum > max_sum : # update max_sum, best_i, best_j max_sum = this_sum; best_i = i best_j = j return best_i, best_j, max_sum Комплексноста на алгоритмот е O(n3) Примерот за најголемата позитивна подсума решен со два вгнездени циклуса def max_subsequence_sum(a): max_sum = 0 best_i, best_j = -1,-1 n = len(a) for i in range(0,n): this_sum=0; for j in range(i, n): this_sum += a[j]; if this_sum > max_sum: Комплексноста на # update max_sum, best_i, best_j max_sum = this_sum алгоритмот е O(n2) best_i = i best_j = j return best_i, best_j, max_sum Назад кон примерот за најголемата позитивна подсума def max_sub_sum( a, left, right ): if left == right: # Base Case if a[left] > 0: return a[left] def max_sub_seq_sum(a): else: return max_sub_sum(a, 0, len(a)-1) return 0 center = (left + right)//2 max_left_sum = max_sub_sum(a, left, center) max_right_sum = max_sub_sum( a, center+1, right);... продолжение Комплексноста на алгоритмот е O(nlog2n) max_left_border_sum, left_border_sum = 0,0 for i in range(center,left-1,-1): left_border_sum += a[i] if left_border_sum > max_left_border_sum: max_left_border_sum = left_border_sum max_right_border_sum, right_border_sum = 0,0 for i in range(center+1, right+1): right_border_sum += a[i] if right_border_sum > max_right_border_sum: max_right_border_sum = right_border_sum return max( [max_left_sum, max_right_sum, max_left_border_sum + max_right_border_sum]) Kadane's algorithm – решение за примерот за најголемата позитивна подсума def max_subsequence_sum(a): i, this_sum, max_sum = 0,0,0 Комплексноста на best_i, best_j = -1, -1 n = len(a) алгоритмот е O(n) for j in range(0, n): this_sum += a[j] if this_sum > max_sum: # update max_sum, best_i, best_j max_sum = this_sum best_i = i best_j = j elif this_sum < 0: i = j + 1 this_sum = 0 return best_i, best_j, max_sum  Споредба на алгоритмите Времиња на извршување на секој од претходните алгоритми Споредба на алгоритмите преку големо О Времиња на извршување на секој од претходните алгоритми Најчести кардиналности Пример Се споредува колку податоци (n) може да обработи секој од алгоритмите за 1, 2, …, 10 секунди: Log Lin LogLin Quad Cub 0:00 0:01 0:10 0:09 0:08 0:07 0:06 0:05 0:04 0:03 0:02 Exp 0 10 20 30 40 50 60 70 80 90 100 n Брзини на растење на различни кардиналности  Нотации T(n) О-нотација Горна граница на времето на извршување на алгоритамот. Ја мери комплексноста (сложеноста) во најлош случај. T(n) T(n) Ω-нотација Долна граница на времето на извршување на алгоритамот. Ја мери комплексноста (сложеноста) во најдобар случај (не е многу корисно). T(n) θ-нотација T(n) Долна и горна граница на времето на извршување на алгоритамот. Се користи при истражување во полето на анализа на алгоритми T(n) Thank you!