Ќе тргнеме од фактот дека алгоритамот ја опишува постапката за решавање на некој проблем во конечен број чекори користејќи точно дефинирани дејства(операции). Тие дејства не се единственото можно решение на проблемот, па од таа причина постојат повеќе различни алгоритми кои решаваат ист проблем.
Како тогаш ќе знаеме кој алгоритам е „оној вистинскиот“? Како ќе знаеме кој алгоритам е подобар? За да одредиме кој алгоритам е подобар потребно е да се одреди мерка за квалитет на алгоритамот, односно потребно е да се измерат ресурсите кои се потребни за да се реши даден проблем. Мерките кои се користат за оценување на квалитетот на една програма се: времето потребно за да се изврши алгоритамот и просторот кој е потребен за чување(меморирање) на влезните податоци, меѓурезултатите и излезните податоци.
Според тоа, сложеноста на алгоритмите може да биде временска и просторна. Просторната сложеност се однесува на анализа на зафатеноста на меморискиот простор при извршување на алгоритамот. Бидејќи денешните компјутери имаат големи мемориски капацитети, вообичаено се пресметува само временската сложеност.
Временска сложеност на алгоритам. Кај временската сложеност на алгоритамот потребно е да се најде мерка која не зависи од брзината на компјутерот, туку од самиот алгоритам.Токму заради тоа, временската сложеност не се изразува со времето потребно за да се пресмета резултатот, туку со бројот на елементарни операции кои алгоритамот мора да ги пресмета за да се добие резултатот.
Временската
анализа на алгоритамот е вид на анализа
во која се разгледува траењето на
извршувањето на конечен број алгоритамски
чекори за да се добие резултат. Самата
анализа не се врзува за временска единица
т.е. не се разгледува времетраењето на
изведба на алгоритмот, туку бројот на
извршување на операции во алгоритмот.
Временската
сложеност не зависи од компјутерот и
неговата брзина на извршување на
алгоритмот, затоа што не сакаме да ја
тестираме брзината на компјутерот, туку
квалитетот на самиот алгоритам.
Анализата ја вршиме на тој начин што ги разгледуваме операциите кои ги извршува компјутерот и ја одредуваме сложеноста на секоја од нив. Откако ќе ја одредиме сложеноста на сите операции можеме да ја изразиме сложеноста на алгоритмот така што ќе ги преброиме сите основни операции кои ги содржи алгоритмот.
Анализата ја вршиме на тој начин што ги разгледуваме операциите кои ги извршува компјутерот и ја одредуваме сложеноста на секоја од нив. Откако ќе ја одредиме сложеноста на сите операции можеме да ја изразиме сложеноста на алгоритмот така што ќе ги преброиме сите основни операции кои ги содржи алгоритмот.
Табела
на сложеност
Наредба
|
Сложеност
|
Коментар
|
0
|
Декларација
на променлива
|
0
|
Придружување
вредност на променлива
|
константа
(c)
|
Аритметичка
операција
|
константа
(c)
|
Операција
на споредување
|
константа
(c)
|
Читање
на вредност
|
константа
(c)
|
Циклус
(while , for ... )
|
Секој
чекор од циклусот има сложеност еднаква
на сложеноста на операцијата која се
извршува во циклусот. Вкупната сложеност
на циклусот е производ на бројот на
чекори и сложеноста на еден чекор.
|
Време
на извршување на алгоритамот
Kога разгледуваме даден алгоритам во него можеме да наидеме на одредени ситуации кога имаме услови и разгранувања кои ја водат програмата во различни насоки на извршување, од кои едната насока може да биде со помала, а другата со поголема сложеност. Од овие причини сложеноста може да се разгледува на три начини:
Kога разгледуваме даден алгоритам во него можеме да наидеме на одредени ситуации кога имаме услови и разгранувања кои ја водат програмата во различни насоки на извршување, од кои едната насока може да биде со помала, а другата со поголема сложеност. Од овие причини сложеноста може да се разгледува на три начини:
- Најдобар случај – оној во кој алгоритамот најбрзо се извршува т.е. има најмал број чекори.
- Најлош случај - оној во кој алгоритамот се извршува во најголем број чекори, но сепак бројот на чекори е конечен.
- Просечен случај- оној во кој имаме можност за извршување во двете насоки а тие имаат просек на вкупниот број на извршувања.
Видови
на анализа на алгоритмите: а priori
и а posteriori.
A
priori анализа
Овој
вид на анализа го проучува траењето на
изведбата на некој алгоритам во најлош
случај. Оваа анализа не зависи од
компјутерот, програмскиот јазик,
компајлерот и сл.
Примери
:
1)
a=a+b ; 1
2)
a=a+b*c ; 2
3) if
(a<5)
{
a=a+b;
}
else
{
a=a+b*c;
b+=a;
} во случај да
не е исполнето a < 5 сложеноста е 3
(најлош случај)
4)
for (i =0 ; i < n ; i++)
{
x+=1;
} сложеноста е
n
5)
for (i=0 ; i < n ; i++ )
{
for
(j=0 ; j < n ; j++)
{
x=i+j;
}
} сложеноста е
n2
A
posteriori анализа
Оваа
анализа, за разлика од A priori анализата,
се спроведува на компјутер, односно се
мери времето на извршување на алгоритмот
на даден компјутер.
Big
O (Големо О) нотација
Големо
O е нотација(ознака) за временска или
просторна анализа на алгоритам или
програма. Најчесто служи за да можеме
отприлика да пресметаме колку ќе трае
извршувањето на дадена програма и колку
меморија ќе зафати.
Објаснување преку примери:
for (i = 0; i < n; i++);
овој циклус се извршува n пати, затоа запишуваме O(n).
for (i = 0; i < n; i++);
for (i = 0; i < m; i++);
првиот циклус се повторува n пати, а вториот m пати, затоа запишуваме O(n+m);
Објаснување преку примери:
for (i = 0; i < n; i++);
овој циклус се извршува n пати, затоа запишуваме O(n).
for (i = 0; i < n; i++);
for (i = 0; i < m; i++);
првиот циклус се повторува n пати, а вториот m пати, затоа запишуваме O(n+m);
for
(i=0;i<n;i++)
{
for(i=0;
i<m;i++);
}
за циклус во циклус, ги множиме броевите на повторување на секој од циклусите, па запишуваме. O(n*m);
}
за циклус во циклус, ги множиме броевите на повторување на секој од циклусите, па запишуваме. O(n*m);
Според
функцијата со која се изразува сложеноста,
постојат следниве видови сложеност на
алгоритми:
- константна О(1)тоа се оние алгоритми во кои се извршуваат само елементарни операции, како собирање, одземање, множење, делење и сл. На пр. Пресметувањето на вредноста на функцијата f(x)=2x+3, не зависи од х, бидејќи операциите множење и собирање имаат приближно исто време на извршување.
- линеарна О(n)ако алгоритамот содржи циклус со n повторувања
- квадратна О(n2)ако алгоритамот содржи два вгнездени циклуси со по n повторувања (циклус во циклус)
- степена О(nк)ако алгоритамот содржи к вгнездени циклуси со по n повторувања
- логаритамска О(log2n)
- линеарно логаритамска О(nlog2n)
- експоненцијална О(kn)
- факториелна О(n!)
Пример
за алгоритми со различна сложеност кои
решаваат ист проблем
Најголем делител на
број
Овој
алгоритам често се наоѓа имплементиран
во различни задачи. Обично се бара НЗД
на два броја. Најголем делител на некој
природен број n е број со кој можеме да
го поделиме n без остаток. Тргнуваме од
наједноставниот алгоритам кој ќе ги
испита сите броеви од 2 до n-1.(секој број
е делив со 1 и сам со себе).
maxdel:=1;
for
(i:=2; i<=n-1; i++)
if
(n %i = = 0) maxdel:=i;
Ако
го разгледаме интервалот (од 2 до n-1) ќе
заклучиме дека нема потреба да се
пребарува понатаму од n/2. Бројот n не
може да се подели без остаток со броеви
поголеми од n/2. Според тоа алгоритамот
може да се модифицира во:
maxdel:=1;
for
(i:=2; i<=n/2; i++)
if
(n %i = = 0) maxdel:=i;
На
тој начин бројот на споредби го намаливме
за половина, а со тоа и времетона
извршување. Ова подобрување на алгоритамот
не може да се забележи на мали броеви,
но секако дека е значително кога се
работи за големи броеви.
број
|
Вкупно
стотинки
(до n-1)
|
Вкупно
стотинки
(до n / 2)
|
500
|
0
|
0
|
5000
|
0
|
0
|
5000000
|
11
|
0
|
4000000000
|
7890
|
3932
|
Понатамошно
подобрување на алгоритмот би направиле
ако го прекинеме циклусот штом го најдеме
најголемиот делител.
Ако
првиот делител на бројот е b, најголемиот
делител ќе биде n / b. Во согласност
со тоа пребарувањето се прекинува штом
се најде првиот најмал делител на бројот,
а најголемиот ќе го пресметаме.
b:=2;
delitel:=false;
do
{
if
(n % b = = 0)
{
maxdel:=n
/ b;
delitel:=true;
}
b++;
}
until
(delitel or (b > n / 2));
Заклучок:
Секогаш треба да размислуваме во насока
на подобрување на алгоритамот. Почнуваме
од најпрегледниот и наједноставниот
алгоритам, кој потоа го подобруваме во
неколку чекори.
