Алгоритам претставува конечно множество на чекори (или постапка) за решавање на одреден проблем. На пример, да речеме дека треба да напишеме програма која ќе прочита N (најмногу 1000) цели броеви и ќе го отпечати, на екран, најголемиот прочитан број. Еден алгоритам за решавање на овој проблем би одел вака: прочитај го N, прочитај ги N-те цели броеви во низа, и потоа провери за секој број од низата дали тој број е најголем. Програмата која го имплементира овој алгоритам е дадена во продолжение:

#include <iostream>
using namespace std;

int main()
{
     int n, p[1000];
     cin >> n;
     
     for (int i=0; i<n; i++)
          cin >> p[i];
     
     int najgolem = -1;
     
     for (int i=0; i<n; i++)
     {
          bool eNajgolem = true;
          
          for (int j=0; j<n; j++)
               if (p[i] < p[j])                   //ima pogolem broj?
                    eNajgolem = false;
          
          if (eNajgolem)
          {
               najgolem = p[i];
               break;
          }
     }
     
     cout << najgolem << endl;
     return 0;
}

Очигледно, оваа програма го решава зададениот проблем. Но, се поставува прашањето, дали постои некој "поефикасен" алгоритам кој го решава истиот проблем? Притоа, постои постапка (наречена анализа на алгоритми) со која може да се предвиди т.н. временска сложеност на еден алгоритам. Под временска сложеност ќе го подразбираме бројот на операции кои се потребни за да се изврши алгоритамот - за познат број на влезни податоци (на пример, N цели броеви). Притоа, се интересираме за најлошото време на извршување на една програма - ако текот на програмата може да тргне во повеќе насоки, нас не интересира онаа која ќе предизвика програмата да се извршува најдолго.

Основата за предвидување на временската сложеност на еден алгоритам е т.н. "големо О" нотација - на пример, O(N²). Притоа, претпоставуваме дека секоја основна операција се извршува во единечно време. За основни операции ќе ги сметаме сите операции кои се извршуваат во фиксно време - аритметички операции, логички операции, читање и печатење на број, доделување на вредност на променлива, итн. Главната цел на постапката е да открие колку брзо се зголемува времето на извршување на програмата со зголемување на големината на проблемот. При пресметување на временската сложеност, ги елиминираме сите членови на изразот освен најзначајниот, како и сите константи. На пример, за алгоритам кој извршува најмногу 4*N² + 3*N + 5 операции, велиме дека има временска сложеност O(N²).

Конкретно, O(N) алгоритам ќе работи двојно (2 пати) побавно при двојно зголемување на големината на проблемот - ако за 1000 броеви алгоритамот се извршува 1 секунда, за 2000 броеви алгоритамот ќе се извршува 2 секунди. О(N²) алгоритам ќе работи четири пати побавно при двојно зголемување на големината на проблемот (2000² = 4000000, што е 4 пати поголемо од 1000² = 1000000) - па ако за 1000 броеви алгоритамот се извршува 1 секунда, за 2000 броеви алгоритамот ќе се извршува 4 секунди. Брзината на извршување на алгоритмите кои имааат O(1) временска сложеност не зависи од големината на проблемот - и за 1000 елементи и за 10000 елементи алгоритамот се извршува 1 секунда.

Да го анализираме следниот алгоритам:

int n, zbir = 0;                  //1 (dodeluvanje na vrednost -> zbir = 0)
cin >> n;                         //1 (chitanje na podatok)

for (int i=1; i<=n; i++)          //2*N+2   -> i=1 (1), i<=n (n+1 pati), i++ (n pati)
      zbir += i*i;                //2*N     -> i*i (n pati), zbir+=... (n pati)

cout << zbir;                     //1 (pechatenje na podatok)

Вкупното времетраење е (1)+(1)+(2*N+2)+(2*N)+(1) = 4*N + 5

При постапката на предвидување на временската сложеност, со цел да го откриеме времето на извршување на еден алгоритам без да навлегуваме во детали како брзина на процесор, диск, итн, ги занемаруваме сите константи од изразот (4*N + 5*1 » N + 1), бидејќи тие варираат од систем до систем - на пример, замислете една програма да се извршува на два компјутери, каде едниот има 4 пати побрз процесор од другиот. Дополнително, ги занемаруваме сите собироци од изразот освен најзначајниот (N+1 » N). За алгоритамот даден погоре велиме дека има сложеност O(N), или линеарна сложеност. Бидејќи нé интересира времето на извршување на програмата за што поголеми вредности на N, ваквата "апроксимација" е логична и не влијае на корисноста на добиениот резултат - дали една програма ќе изврши N операции или N+1 е ирелевантно за големи вредности на N.

На пример, програма која имплементира алгоритам со сложеност N²+N, за N=10 000 ќе изврши околу 100 000 000 + 10 000 = 100 010 000 операции. Јасно се гледа дека членот N не влијае сериозно на времето на извршување на програмата - 10 000 пати е понезначаен од другиот член (N²) на изразот (при 100 010 000 извршени операции - гледано во бројот од лево на десно, N влијае дури на 5-тата по значајност цифра). За уште поголема вредност на N - на пример N=1 000 000, вториот член во изразот (N) има уште помало влијание - околу 0.0001% од вкупниот број на операции.

Важно е да напоменеме дека, доколку сложеноста зависи од повеќе параметри и немаме некоја информација за тоа како параметрите зависат едни од други или кој параметар доминира во пресметките (на пример, имаме N студенти и M професори и за секој од нив треба да извршиме некоја операција), можно е и изразот да зависи од повеќе променливи, односно да е од типот: O(N+M), О(N*M), или нешто сосема друго.

Бидејќи се интересираме за најлошото време на извршување на програмите, ќе ги користиме следниве правила за пресметка на временската сложеност:

Од сé што кажавме досега, може да се заклучи дека е едноставно да се открие временската сложеност на една програма преку анализирање на циклусите. Навистина, оној циклус кој е најмногу вгнезден во други циклуси ќе доминира со времето на извршување на програмата (нормално - доколку сите циклуси зависат од ист параметар). Користејќи го ова правило, може да заклучиме дека првата програма која што ја прикажавме има временска сложеност O(N²) - циклусот кој проверува дали тековниот број е најголем ќе доминира при анализата на временската сложеност.

#include <iostream>
using namespace std;

int main()
{
     int n, p[1000];
     cin >> n;
     
     for (int i=0; i<n; i++)
          cin >> p[i];
     
     int najgolem = -1;
     
     for (int i=0; i<n; i++)
     {
          bool eNajgolem = true;
          
          for (int j=0; j<n; j++)
               if (p[i] < p[j])                          //ima pogolem broj?
                     eNajgolem = false;
          
          if (eNajgolem)
          {
               najgolem = p[i];
               break;
          }
     }
     
     cout << najgolem << endl;
     return 0;
}

Можеби, во овој момент, се прашувате зошто се интересираме само за најлошиот случај на извршување на програмата и велиме дека временската сложеност е O(N²). Што ако уште првиот елемент е најголем и се изврши наредбата break; - тогаш програмата очигледно нема да изврши N² операции. Навистина, при некои анализи може да се интересираме за т.н. најдобро време на извршување, или, уште почесто, за просечното време на извршување на една програма. Во просек, програмата дадена погоре ќе измине N/2 цели броеви и за секој од нив ќе провери дали е тоа најголемиот прочитан цел број.

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

На пример, што ако имаме две програми кои се поставени на два компјутери поврзани на Интернет и истите се повикуваат од посетители на некој сајт. Притоа, едната програма има просечно време на извршување од 1 секунда и најлошо време на извршување од 2 секунди, додека другата програма има просечно време на извршување од 0.02 секунди и најлошо време на извршување од 200 секунди. Втората програма, во просек, е многу побрза од првата - но може да предизвика сериозен проблем доколку се појават податоци поради кои таа би работела 200 секунди. Тогаш, ќе мора да се чека 200 секунди за некој следен посетител да може да прави пресметки. Сега, замислете дека работите за Google и споредувате алгоритми за пребарување на податоци - сигурно веднаш ќе ги отфрлите алгоритмите кои треба да се извршуваат со минути. Од друга страна пак, ако можете да ја откриете поврзаноста на влезните податоци со времето на извршување, тогаш можете од двата алгоритми да направите еден нов алгоритам кој ќе ги поседува и двата атрибути - одлично просечно време на извршување и одлично најлошо време на извршување.

Проблемот што го дискутиравме погоре (откривање на најголем цел број) може да се реши и со друг алгоритам. Следнава програма има најлоша временска сложеност O(N):

#include <iostream>
using namespace std;

int main()
{
     int n, t, najgolem = -1;
     cin >> n;
     
     for (int i=0; i<n; i++)
     {
          cin >> t;
          
          if (t > najgolem)
               najgolem = t;
     }
     
     cout << najgolem << endl;
     return 0;
}

Сега може да заклучиме што ни овозможува анализата на временската сложеност - да споредиме два алгоритми кои решаваат еден ист проблем и без да ги пишуваме програмите на компјутер. Денешните компјутери можат да извршат околу 100 000 000 операции за 1 секунда (зборуваме за основните операции дефинирани на почетокот - наредбите за читање, печатење, аритметичките операции, итн...). Знаејќи го овој податок и временската сложеност на еден алгоритам, можеме да пресметаме, за дадени ограничувања на влезните податоци, дали една програма ќе заврши во потребните временски рамки или не. На пример, алгоритам со сложеност O(N) може, без никакви потешкотии, да реши проблем на откривање на најголема вредност во низа со 50 000 елементи.

Пребарување на податоци

Да замислиме дека е потребно да напишеме програма која, за N студенти (на пример, 20 посетители на некој курс), ќе ги отпечати нивните е-маил адреси. Студентите се чуваат во низа student, која е составена од податоци од тип Student - се чува број на индекс, име, презиме, е-маил и телефон. Основниот дел од програмата би изгледал вака:

int N;
cin >> N;

for (int i=0; i < N; i++)
{
     //za kogo treba da najdeme e-mail?
     int indeks;
     cin >> indeks;
     
     //najdi e-mail
     string email = najdiEMail(indeks);
     cout << "Emailot na studentot so indeks " << indeks << " e " << email << endl;
}

Колкава е сложеноста на овој дел од кодот? Според сé што дискутиравме досега, сложеноста е O(N), така? Имаме еден for циклус кој чита број на индекс за N студенти и ги печати нивните е-маил адреси.

Погрешно! Бидејќи не знаеме колку операции ќе се извршат во функцијата najdiEMail(int indeks), гледајќи го само овој дел од програмата и не можеме да заклучиме колкава е сложеноста на алгоритамот. Многу е веројатно во функцијата за наоѓање на е-маил да постои некој циклус кој би се движил низ низата student и би пребарувал студенти со одреден број на индекс:

string najdiEMail(int indeks)
{
     for (int i=0; i<brojStudenti; i++)
          if (student[i].indeks == indeks)
               return student[i].email;
     
     return "GRESHKA! Nema takov student.";
}

Дури сега можеме да дадеме заклучок за сложеноста на алгоритамот за наоѓање на e-mail адреси за N студенти - тоа е O(N*M), каде N е бројот на студенти за кои треба да најдеме e-mail адреса, а M е вкупниот број на студенти во системот (во горниот дел од кодот, тоа е променливата brojStudenti).

Дали постои начин на кој може да го подобриме алгоритамот? Доколку студентите се ставени во низа која не е подредена според бројот на индекс, тогаш немаме друг избор: мора да го извршуваме горенаведениот алгоритам - почнувајќи од првиот студент, за секој проверуваме дали неговиот број на индекс е еднаков на бараниот.

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

Како бараме телефонски број во телефонски именик? Еден начин на кој може да пребаруваме оди вака: Доколку именикот има 2 000 000 записи, провери го 1 000 000 запис (оној во средината). Да речеме дека 1 000 000 запис е човек со име "Марковски Петар". Ако имаме неверојатно многу среќа и сме го погодиле точно човекот кој го бараме, тогаш го враќаме неговиот број. Но, доколку тоа не е човекот што го бараме, може веднаш да елиминираме голем број од записите - ако бараното лице е во првата половина од именикот (на пример, презимето на човекот што го бараме почнува на буква која во азбуката се наоѓа пред M), можеме веднаш да отфрлиме половина од именикот (втората половина). Слично, доколку човекот е во втората половина, можеме да ја отфрлиме првата половина од именикот. Доколку ја повторуваме оваа постапка (наречена бинарно пребарување) повеќе пати - неверојатно многу брзо ќе дојдеме до бараниот телефонски број. На пример, за телефонски именик со 2 000 000 записи, потребно е да направиме најмногу 21 споредба.

Конкретно, за телефонски именик со 1 запис - потребна е една споредба. За именик со 2 записи, потребни се 2 споредби. За именик со 3 записи, потребни се (најмногу) 2 споредби. Понатаму:

• за именик со 7 записи, потребни се најмногу 3 споредби.
• за именик со 15 записи, потребни се најмногу 4 споредби.
• за именик со 127 записи, потребни се најмногу 7 споредби.
• за именик со 1023 записи, потребни се најмногу 10 споредби.
• за именик со 1048575 записи, потребни се најмногу 20 споредби.
• за именик со 1073741823 записи, потребни се најмногу 30 споредби.

Забележете колку бавно расте оваа функција. За алгоритмите со вакво однесување се вели дека имаат логаритамска сложеност O(logN) - бидејќи обратната математичка функција од степенување (c^x) се нарекува логаритмирање. Не е важна основата на логаритамот - на сличен начин како што ги отфрлавме константите во претходните анализи, сега може да делиме на 2 дела, на 3 дела или на 10 - сложеноста повторно ќе биде O(logN).

Проблем на патувачки трговец

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

На пример, да ги разгледаме можните патеки за N=3 градови (Париз, Мадрид и Лондон).

(1 -> 2 -> 3)       Париз -> Мадрид -> Лондон
(1 -> 3 -> 2)       Париз -> Лондон -> Мадрид
(2 -> 1 -> 3)       Мадрид -> Париз -> Лондон
(2 -> 3 -> 1)       Мадрид -> Лондон -> Париз
(3 -> 1 -> 2)       Лондон -> Париз -> Мадрид
(3 -> 2 -> 1)       Лондон -> Мадрид -> Париз

За N=3 градови имаме вкупно 6 можни патеки. За N=4 имаме 24 можни патеки. За N=5 имаме 120, за N=6 имаме 720, za N=7 имаме 5040, за N=8 имаме 40320, ..., за N=20 имаме 2432902008176640000 патеки, итн. Доколку должината на патеките не зависи од насоката (должината од Лондон до Париз е еднаква на должината од Париз до Лондон), можно е да скокнеме дел од патеките - но нишно значително.

Математички, зборуваме за операција наречена факториел - N!

3! = 3*2*1 = 6
4! = 4*3*2*1 = 24
5! = 5*4*3*2*1 = 120
6! = 6*5*4*3*2*1 = 720

Доколку го решаваме овој проблем така што ќе ги анализираме сите патеки и на крајот ќе ја одбереме најкратката, сложеноста на алгоритамот е О(N!).

Во следната табела се дадени сите сложености кои ги споменавме досега, како и други сложености кои често се среќаваат при решавање на алгоритамски задачи:

Како што ќе разгледуваме нови алгоритми, така ќе ја анализираме и нивната временска сложеност. Засега, доволно е да знаете што е тоа временска сложеност, зошто е таа важна, како да анализирате поедноставни програми преку разгледување на нивните циклуси, и да имате предвид дека постои голема разлика во брзината на извршување на алгоритмите со различна временска сложеност (линеарна, логаритамска, факториелна, итн).

Дозвола за користење: CC BY-NC 2.5 ©