Лекция №3 Сложност на алгоритмите



Дата02.02.2018
Размер49.53 Kb.


Технически университет - Габрово

Катедра “Компютърни системи и технологии”

Учебна дисциплина ”Синтез и анализ на алгоритми”

Специалност “КСТ”

Курс 2

Редовно обучение

Степен “Бакалавър”

Лекция № 3

Сложност на алгоритмите

За да можем да сравняваме различните алгоритми за една и съща задача и да изберем най-подходящия за конкретния случай се използват различни характеристики на алгоритмите. Често използвани са следните 4 характеристики на алгоритмите:



  1. 1.Време за изпълнение на алгоритъма (времева сложност, сложност по време, бързодействие, time complexity) – Т.

  2. Необходима памет (сложност по памет, space complexity) – това е средното количество информация, която трябва да се помни по време на изпълнение на алгоритъма – П.

  3. Дефиниционна област на алгоритъма, определена от набора от задачи - ДО

  4. Точност- отнася се само за числените алгоритми, в които основни са аритметичните операции с числа от реален тип. Не се отнася за алгоритмите, работещи с цели числа и символна информация, които не допускат грешка. Тази характеристика показва каква е максималната грешка, която алгоритъма допуска в резултата.

  5. Размер на задачата (или входен размер)- това е величина, която показва какво е количеството на входните данни на дадения алгоритъм (най- често се означава с n). Размерът на задачата е мярка за количеството входни данни и обикновено е равен точно на броя на входните данни, но не винаги. Сигурно е обаче, че ако расте количеството данни, расте и n. В някои случаи размерът на задачата се изразява с броя на битовете, необходими за представяне на входните данни.

Времето Т за изпълнение на даден алгоритъм може да се представи като функция на размера n на задачата, т.е. Т( n) и това е времевата сложност. Същото може да се каже и за сложността П(n) по памет. Конкретната функция на времевата сложност T(n) зависи от конкретния компютър, на който се изпълнява алгоритъма. T(n) може да се изрази, обаче и независимо от изпълнителя на алгоритъма, чрез броя на операциите (които той извършва при изпълнението си) като функция на n. На практика, обаче не се отчитат всички операции, а само една или две, основни, главни, които са най-трудоемки и се изпълняват най-голям брой пъти в алгоритъма.

Определянето на сложността на даден алгоритъм се нарича анализ на алгоритъма. При един и същ компютър и едно и също n времето за изпълнение не е едно и също, а зависи от конкретните входни данни – има минимално Тmin и максимално Тmax време наричани съответно минимална и максимална сложност. Имаме и средна сложност Тср.(n) – това е средното време от времената за всички случаи при дадено n. Тmax се определя по- лесно от Тср., т.к. за последната трябва да се определя броя на случаите и сложността за всеки случай и често се налага вероятностен анализ, а не просто определяне на средноаритметично време.

Определянето на сложността е понякога изключително трудна задача и заема много страници аналитични изследвания. Точната функция на сложността на алгоритъма се определя от броя на операциите, извършвани при неговото изпълнение.

За всеки блок Бi (или оператор) се определят две величини: броя ti на операциите в него и броя ni на неговите изпълнения, от които се определя сложността на блока tini. Ако за всички блокове се знаят величините ti и ni, тогава общата сложност на алгоритъма

m

Т (n) = ∑niti ,



i=1

където m е броят на блоковете на алгоритъма.


Най-трудният проблем, обикновено, е определянето на броя на изпълненията на тялото на цикъл. При анализа на алгоритъм важи закон, подобен на първия закон на Кирхорф за електрическите вериги. Този закон гласи: Сумата от броевете на изпълнение на входните стрелки в даден блок е равна на сумата от броевете на изпълнение на изходните стрелки от този блок :

m i n j

∑ nвх = ∑ nизх .

i=1 j=1


За някои алгоритми може да се определи точната функция Т(n) на времето на изпълнение, но в повечето случаи това се оказва трудна и невъзможна задача. По-удачно и по-лесно е определянето на друга функция, която да е някаква граница (най-често горна) на Т(n). Това е т.н. асимптотична сложност. При нея се отчитат най- важните членове в израза на Т(n), а другите се пренебрегват. Асимптотичната сложност оценява сложността на алгоритъма за големи стойности на n (n → ∞). При нея е важна скоростта на нарастване на функцията. Функциите се сравняват по своята скорост на нарастване.
За тази цел се въвеждат следните означения (видове асимптотична сложност):

1. Т(n) = O(f(n)), ако съществуват положителни константи C>0, no>0, такива че Т(n)≤C.f(n) за n≥no , т.е. Т(n) расте по- бавно или със скорост равна на f (n) – f(n) е горна асимптотична граница на Т(n).

2. Т(n) = Ω(f(n)), ако съществуват положителни константи C>0, no>0, такива че Т(n)≥C.f(n) за n≥no , т.е. Т(n) расте по- бързо или със скорост равна на f (n) – f(n) е долна асимптотична граница на Т(n).

3. Т(n) = θ(f(n)), ако Т(n) = О(f(n)) и Т(n) = Ω(f(n)), т.е. Т(n) и f(n) растат с една и съща скорост.

4. Т(n) = о(f(n)), ако Т(n) = О(f(n)) и Т(n) ≠θ(f(n)), т.е. Т(n) расте с по-малка скорост от f(n) (за разлика от О(f(n)) тук равенството липсва).
Съществуват общи правила при определяне на сложността на алгоритъма.


  1. При цикъл for сложността е равна на броя на изпълненията на цикъла, умножен по сложността на тялото.

  2. При вложени цикли for общото време е равно на времето на тялото на цикъла умножено по произведението на броевете на изпълнение на всеки цикъл.

Например при 3 вложени цикъла :

for i :=1 to n1 do

for j :=1 to n2 do

for k :=1 to n3 do ОП;

сложността е n1.n2.n3.t, където t е времето за изпълнение на тялото ОП на вътрешния цикъл.

3. При последователно изпълнение на оператори ( съставен оператор begin ОП1;ОП2;ОП3;...... ОПn; end ) времената на всички оператори се сумират, но максималната сумарна сложност се определя от оператора с максимална сложност.

4. При условния оператор if условие then ОП1 else ОП2 сложността се определя от времето за проверка плюс по- голямото от двете времена на ОП1 и ОП2.


ВЪПРОСИ И ЗАДАЧИ

за самостоятелна работа



  1. Опишете и представете чрез блокова схема двата алгоритъма за решаване на едно пълно квадратно уравнение с едно неизвестно от вида а.х2 + b.х + с = 0.

  2. Определете и сравнете сложността на двата алгоритъма.

  3. Опишете с блокова схема алгоритъма за пресмятане на лице на триъгълник със страни а, b и с (различни от нула по стойност) по формулата на Херон:

S = ( p(p-a)(p-b)(p-c) ) –1/2 , където: p = (a + b + c).1/2

Алгоритъмът да включва предварителна проверка на условията за съществуване на триъгълника:



a < b + c ; b < a + c ; c < a + b .

  1. Определете сложността на алгоритъма и характеризирайте неговите особености от тази гледна точка.

  2. Сравнете сложността на два от алгоритмите за решаване на система линейни уравнения (например: изберете два от методите на Гаус, Жордан или Кроут).




База данных защищена авторским правом ©obuch.info 2016
отнасят до администрацията

    Начална страница