Пример 3

Пример 4

Дадени се алгоритми во пример 3 и 4. Кој од нив не е правилен алгоритам? Зошто?

(Одговор:Aлгоритмот од пример 3 не е правилен, бидејќи ако бројот а е помал од бројот b, тогаш циклусот ќе се извршува бесконечно и никогаш нема да се добие резултат (решение).

Исто така и алгоритмот во пример 4 не е правилен, бидејќи во него постои дел кој никогаш не се извршува. Делот печати m,’=’,n; во внатрешната ако-тогаш-инаку контролна структура никогаш нема да се изврши.)

За даден проблем може да се напишат различни алгоритми и сите тие да бидат правилни. Ако се правилни секој од нив ќе даде точно решение. Но тоа не значи дека сите тие алгоритми се подеднакво ефикасни. Некој можеби ќе биде побрз, друг да дава поточни резултати, трет да има пократок запис или да биде појасен итн.
Но секој од тие алгоритми треба да ги има следниве особини:

• секоја операција е точно определена
• во алгоритмот е прецизно утврден редоследот на извршувањето на операции
• алгоритмот може да се расчлени на елементарни чекори
• дава резултати по конечен број чекори
• со алгоритмот се опфатени сите можни решенија за различни вредности на влезните податоци
• не зависи од тоа дали се извршува од човек или на сметач,и тоа независно од типот на сметачот
• да е разбирлив за секој,независно кој го напишал

Споменавме дека може да се напишат повеќе правилни алгоритми за ист проблем. Тогаш се поставува прашањето кој алгоритам да се користи? Кој алгоритам е подобар?
Лесно е да кажеме овој алгоритам е подобар од другиот, но како сме дошле до тоа сознание, зошто едниот е подобар од другиот алгоритам?
Овие прашања имаат одговор кој води до анализа на алгоритмот и одредување на неговата сложеност.

4. Анализа на алгоритмот

Претпостави дека компјутерите се бесконечно брзи и компјутерската меморија слободна.Дали би имале било каква причина да учите алгоритми? Одговорот е да, ако не за друго да докажите дека вашето решение завршува и го дава точниот одговор.
Ако компјутерите се бесконечно брзи, секој точен метод за решавање на одреден проблем ќе работи. Вие сигурно сакате вашата имплементација да биде добро дизајнирана и документирана но многу често го користите методот што е најлесен за имплементација.
Секако, компјутерите можеби се брзи, но не се бесконечно брзи. И меморијата можеби е ефтина но не е неограничена. Времето за пресметка е исто така ограничувачки ресурс, како што е просторот во меморијата. Овие ресурси треба да се користат мудро, и алгоритмите ќе бидат поефикасни во однос на времето и меморијата.

Анализата на алгоритмот овозможува да се даде квантитативна оценка за предноста на еден алгоритам во однос на друг алгоритам за ист проблем. Оценката може да преставува како алгоритмот се однесува во:

• најдобар случај
• најлош случај
• просечен случај

Значи анализата на алгоритмот се прави за да може полесно да се спореди со друг алгоритам за истиот проблем. Со анализирањето на алгоритмите и определување на најдобриот алгоритам од понудените за тој проблем значително се заштедува на време и пари и се добива поголема ефикасност во решавањето на зададените задачи.

Ќе се запрашаме што точно се оценува кај еден алгоритам? На кој начин се споредуваат два алгоритми?
Еден начин за споредба на алгоритмите е да се споредат кој побрзо го решава дадениот проблем. Некои доаѓаат побрзо до решението од другите. Најчесто и ние го одбираме алгоритмот што најбргу доаѓа до решението.

Друг начин за споредба на алгоритмите е да се види колку мемориски простор е потребен при извршување на алгоритмот напишан во програмски јазик. Некои од нив зафаќаат повеќе мемориски простор, но бргу доаѓаат до решението, а други помалку мемориски простор, а до решението доаѓаат поспоро.

Значи сложеност  е ниво на тежина при решавање на одреден проблем мерен во време, број на чекори или аритметички операции, меморија.

Ние ќе се задржиме на временската сложеност на алгоритмот.
Времето што е потребно за решавање на одреден проблем зависи од одреден број на фактори:

• колку е брз компјутерот
• капацитетот на RAM-от на компјутерот
• оперативниот систем
• квалитетот на кодот генериран од компајлерот итн.

Ако некој од факторите се промени тогаш и времето на извршување се менува.

Затоа оваа големина не е доволно добра како мерка за алгоритамските перформанси. Нас ни е потребна мерка со која ќе може да споредиме 2 алгоритми.

Анализата на алгоритмот се состои од 2 фази:

• претходна анализа
• тестирање

Во првата фаза, претходна анализа, се формира функција на сложеност зависна од релевантни фактори која го определува времето на извршување. Функцијата всушност преставува оценка на алгоритмот кога тој не зависи од тоа на каков компјутер се извршува.

На кој начин се прави тоа?

Секој алгоритам се состои од конечен број инструкции. Колку повеќе иструкции, толку подолго тој ќе се извршува. Еден начин е да се бројат инструкциите (операциите) од кој е составен алгоритмот за решавање одреден проблем. Потребно е да се знае колку пати се извршува инструкцијата и која е “нејзината цена” т.е. времето (честота) на едно извршување на инструкцијата.

Нека се дадени следниве програмски сегменти:

а) честота на извршување е 1
б) честота на извршување е n
в) честота на извршување е n²

Бројот на инструкции ќе варира зависно од бројот на внесените податоци. Програма за пресметка на плати, за влез од 100 лица ќе изврши повеќе инструкции одколку за 10 лица. Затоа може да го изразиме бројот на инструкции како функција на сложеност од бројот на внесени податоци.

Пример 5

Функцијата што го преставува бројот на инструкции за овој алгоритам може да се запише како f(n)=2n+7. Оваа функција на сложеност е линеарна, што значи и сложеноста на овој алгоритам е линеарна. Но мора да напоменеме дека оваа функција е зависна од сметачот  и програмскиот јазик во кој се извршува.

Нека f(n) е функција на сложеност што зависи од компјутерот на кој се извршува алгоритмот, а g(n) функција на сложеност што не зависи од тоа на каков компјутер се извршува алгоритмот. Тогаш важи f(n)=O(g(n)). Кога ќе се каже ...Алгоритмот има O(g(n)) време на пресметување (извршување)... Тоа значи дека ако алгоритмот се извршува повеќе пати на иста машина, на ист тип податоци, но за различно (растечко) n, времето на извршување секогаш ќе биде помало од некоја константна вредност |g(n)|.

Значи функцијата на сложеност која не зависи од тоа на каков сметач се извршува алгоритмот во примерот 5 е g(n)=n, и велиме алгоритмот има сложеност О(n) (се чита “од ред n ”).

Но дали треба да ги земеме во предвид сите инструкции во алгоритмот?

Најчесто алгоритмите се состојат од циклус и инструкции што се извршуваат во него или надвор од него. Бројот на инструкциите надвор од циклусот во алгоритми што се однесуваат за ист проблем незначително се разликува. Од нив не зависи дали алгоритмот ќе има помала или поголема сложеност. Ако бројот на влезни податоци расте тогаш бројот на инстукции што се извршуваат во циклусот го надминува бројот на оние што се надвор од него. За да ја упростиме нашата пресметка  нема да ги броиме инструкциите надвор од циклусот.

Дали треба да ги земеме во предвид сите инструкции во циклусот?

Бројот на инструкции во циклусот незначително се разликуваат во 2 алгоритми напишани за ист проблем. Но, тоа што се разликува е колку пати циклусот се извршува.

Пример 6

Потребно е да го пресметаме бројот на извршувања на циклусот. Во алгоритам кој пребарува низ низа елементи, во циклусот се споредува тековниот елемент од низата со елементот што треба да се најде. Во овој случај го бараме бројот на споредувања на елементите во дадениот алгоритам. Но бројот на споредби пак зависи од должината на низата. Нека низата има должина n, во алгоритам за линеарно пребарување. Бројот на споредувања ќе биде n кога елементот што се бара не е во низата. Тогаш велиме дека алгоритмот има сложеност О(n) или линеарна сложеност.

Ако ја зголемиме двојно низата, двојно се зголемува и бројот на споредби во алгоритмот. Но некогаш имаме среќа да го најдеме елементот блиску до крајот, а некогаш блиску до почетокот на низата. Во тие случаи ни треба да ја пребараме половина од низата за да го најдеме тој елемент. Па тогаш би имале О(n/2) споредувања. Ова се нарекува просечна сложеност на алгоритмот. Ако пак елементот не се наоѓа во низата, се прават n споредувања и ова се нарекува најлош случај на сложеност на алгоритмот. Но да забележиме дека сепак сложеноста на алгоритмот е О(n) наспроти фактот дека во просек се прават n/2 споредби.

Ова е поради тоа што ако n расте многу големо, разликата помеѓу n и n/2 станува се помалку значајна. Кога се споредува алгоритам важно е да се знаат и двете сложености (просечна и најлошиот случај).

Ќе опишеме друг алгоритам за барање низ низа наречен бинарно пребарување (Binary Search) кaде бројот на споредувања е значајно помал. Тој изнесува О(log n).

Пример 7

Ако имаме низа со должина 1000 со бинарно пребарување би го нашле бараниот елемент во најлош случај со 10 споредби (обратно од линеарното пребарување). Но низа со должина 1 билион во најлош случај го наоѓа елементот по 30 споредувања. Очигледно е дека бинарно пребарување е со помала сложеност од линеарното пребарување. Бинарното пребарување се состои од делење на низата на половина и воочување во која од двете добиени низи е бараниот елемент. Потоа таа низа повторно се дели на половина инт., се додека не се пронајде елементот или пак додека не се воочи дека елементот не е во низата.

Во најлош случај бинарното пребарување престанува кога нема да го најде елементот во низата. По i-тото делење на низата на пола, кандидати за елементот што се бара се најмногу n/2i.  Кога ќе заврши процесот i е најмалиот цел број  така што (n/2i )log n. Значи алгоритмот се изведува во време О(log n).

Бинарно пребарување има ограничено користење т.е. само кога низата е сортирана. Тоа е метод кој го користиме кога листаме телефонски именик. Отвараме на “средина” и во зависно од тоа каде сме отвориле знаеме дали бројот е во едната половина од именикот или во втората половина. Со ова елиминираме половина од именикот со едно споредување. Оваа постапка се повторува на делот што останува додека не се најде бројот или додека не се утврди дека не се наоѓа во низата, cо што секоја натамошна споредба ја намалува низата за половина.

Но како што рековме за да го користиме овој метод низата треба да е сортирана. Алгоритмите за пребарување и сортирање се повеќе се користат. Па всушност скоро во секој алгоритам за поголем проблем има сортирање и пребарување.

Ќе покажеме алгоритам за сортирање наречен метод на меурче (Bubble Sort).

Има многу начини да се сортира низа. Подолу ќе ја објасниме метода на меурче(Bubble Sort) и ќе ја покажеме нејзината сложеност. Ќе ја сортираме низата во растечки редослед. Нека низата е: 10, 34, 2, 16, 23, 8, 12. Сакаме да добиеме 2, 8, 10, 12, 16, 23, 34. За да ја сортираме мора да ги знаеме вредностите на елементите во низата, така што елементите со помала вредност ќе ги заменат местата со оние со голема вредност, со што големите вредности  ќе дојдат на крајот, а малите на почетокот на низата. Сакаме да ги поместиме големите вредности на крајот од низата. Може да споредуваме само 2 вредности од низата. Во овој метод почнуваме од почетокот на низата. Ги споредуваме првите 2 елементи L[0] и L[1].Ако L[0]>L[1] тогаш смени им ги местата. Потоа ако L[1]>L[2] тогаш смени им ги местата итн. Ова го поместува најголемиот елемент на крајот на низата. Другиот дел од низата не е сортирана. Сме поминале низ низата еднаш. Низата ја има формата 10, 2, 16, 23, 8, 12, 34. Потоа почнуваме пак од почеток со горенаведената постапка. И се така до моментот кога ќе ја пројдеме низата по n-ти пат ако таа има должина n. По завршувањето на методот низата е следна: 2, 8, 10, 12, 16, 23, 34 и е сортирана. Оваа метода се нарекува така затоа што елементот се движи кон крајот на низата како меурче во чаша вода за да излезе на површина. Поголемото се движи побрзо кон површината.

Задача:

Со метод на меурче да се сортира низата 2,4,15,6,7,9,10. Колкава е сложеноста на алгоритмот во овој случај?

Сложеноста на метод на меурче за низа од n елементи е О(n²). Зошто?
Низа од n елементи, со овој метод ја поминуваме n пати, а во секое поминување на низата правиме n споредби на елементите. Од таму сложеноста на овој алгоритам е О(n²).

Досега видовме сложеност на 3 алгоритамски методи:

• Линеарно пребарување O( n )
• Бинарно пребарување O(log n)
• Метод на меурче O(n2)

Сложеноста на алгоритмите со низи е најмалку О(n) бидејќи скоро секогаш мора да поминеме барем еднаш низ низата. Бинарното пребарување е на некој начин исклучок. Предноста е во тоа што не мора да се поминува целата листа која е сортирана. Но што ако низата не е сортирана? Тогаш или ќе користиме линеарно пребарување што се користи и за несортирани и сортирани низи или прво ќе ја сортираме низата, а потоа ќе употребиме бинарно пребарување. Линераното пребарување ќе биде подобро од комбинацијата сортирање и бинарно пребарување. Алгоритам со сложеност O(n) е поефикасен алгоритам во споредба со метод на меурче со сложеност O(n²).

Според сложеноста на алгоритмите разликуваме:

• константни                                         О(1)
• линеарни                                             О(n)
• логаритамски                                      О(log2 n)
• линеарно-логаритамски                    О(n∙log2 n)
• квадратна                                            О(n2)
• експоненцијални                                О(2n) (n>1)
• факториелни                                       О(n!)

Колку помала сложеност толку поголема ефикасност има алгоритмот. Нормално ние ќе го избереме оној алгоритам со најмала сложеност. Од горе наведените алгоритми најефикасни се логаритамските, а видовме и зошто.
Постојат голем број на линеарни алгоритми кои се ефикасни,а квадратните алгоритми имаат добра ефикасност.

Експоненцијалните и факториелните алгоритми имаат многу мала ефикасност и се користат само кога мора. Постојат проблеми за кои има пронајдено само експоненцијални или факториелни алгоритми.  Наоѓањето на алгоритам со помала сложеност за таков проблем е голем успех.

Втората фаза од анализата на алгоритмот е неговото тестирање на машина во некој програмски јазик. Многу од програмите кои се користат содржат багови (грешки). Секој (чесен) програмер  ќе ги преброи глупавите, смешни и сериозни грешки што ги направил во програмата. Дури и ќе се обиде да ги поправи и во секое наредно пишување на алгоритам за било кој проблем ќе гледа да не ги повтори. 70% од конструирањето на нов комплексен софтвер се троши за поправање на грешките. Почетниците најчесто веруваат дека нивните алгоритми го прават токму она што тие сакаат да го направат и дека тие алгоритми се најефикасните.

При тестирањето не може да се задржиме на функцијата на сложеност од претходната анализа, туку треба да се води сметка и за константите што се јавуваат во таа функција.

Прашање:

Ако имаме два алгоритми кои истата задача ја извршуваат со n влеза, и првиот има време на пресметување O(n), а вториот O(n2), кој е побрз?

Со сигурност ќе тврдиме дека првиот е побрз. Лесно е да се забележи дека за доволно големи вредности на n, времето на извршување на вториот алгоритам ќе биде поголемо од времето на извршување на првиот.

Нека вистинско време на извршување на алгоритмот на сметач е 2n и n2 соодветно.Тогаш првиот алгоритам е побрз за сите n>2.

Проблем: Што ако 104n и n2 се соодветните вистински времиња на извршување?

Тогаш вториот алгоритам е побрз за сите n104, побрз е првиот алгоритам. Значи не може да одлучиме кој алгоритам е побрз, ако не знаеме ништо за константите поврзани со функцијата на сложеност.

Методите во оваа фаза може да се групираат во две категории: тестирање и докажување. Тестирањето се состои од извршување на програмата за разни влезни податоци и дали ќе даде точен резултат за тие податоци.Тестирањето се врши само над одбрано множество влезни податоци. Докажувањето на програмата значи дека програмата е исправна за сите дозволени влезни податоци (од различен тип), дури и за голем број на влезни податоци. Тестирањето повеќе се користи бидејќи е полесна техника за проверка на исправноста на алгоритмот. Докажувањето на алгоритмот се користи за резонирање на однесувањето на програмата. Со него може да се зголеми довербата во исправноста на програмата.

5. Ефикасност

Алгоритмите што се смислени да решат ист проблем често драматично се разликуваат во нивната егикацност. Овие разлики можат да бидат позначајни од разликите во хардверот и софтверот.
Како за пример, ќе видиме два алгоритми за сортирање. Првиот, или уште попознат како инсертион сорт, зема време n2 за да сортира n работи. Вториот, merge sort, истите работи ќе ги сортира за време log2n. Вреди да се спомене тоа што insertion sort е обично побрз од merge sort за мали вредности на n, но кога бројот на внесени податоци доволно ќе нарасне merge sort е убедлив во однос на insertion sort.
За конкретниот пример, нека имаме компјутер А којшто е побрз и ќе равоти со insertion sort и компјкутер Б којшто е поспор и ќе работи со merge sort. Нивна задача е да сортираат низа од 1000000 броеви. Да претпоставиме дека компјутерот А извршува 1 билион инструкции во секунда, а компјутерот Б извршува само 10 милиони инструкции во секунда. Значи компјутерот А е 100 пати побрз од компјутерот Б. За да ја направиме разликата уште повеќе драматична нека константите ц1 за компјутерот А биде 2, а ц2 за компјутерот Б биде 50. За да сортира еден милион броеви, на компјутерот А ќе му требаат

додека на компјутерот Б ќе му требаат:

Со користење на алгоритам чиешто вреем на извршување расте многу поспоро, дури и со послаб компајлер, компјутерот Б работи 20 пати побрзо отколку компјутерот А! Предноста на merge sort ќе биде уште поизразена кога би сортирале 10 милиони броеви: кога на insertion sort би му требале приближно 2,3 дена, додека на merge sort помаалку од 20 минути. Генерално, колку големината на проблемот се зголемува, толку се золемува предноста на merge sort.

Псевдокод на mergeSort во Pascal

Псевдокод на mergeSort во Java