Поред својства исправности програма, важно питање за практичну примену је колико ресурса програм захтева за своје извршавање. Најважнији ресурси су време потребно за извршавање програма и количина меморије заузете током извршавања (мада се могу анализирати и други ресурси, на пример, код мобилних уређаја важан ресурс је утрошена енергија). У складу са овим, разматрају се:
Просторна сложеност односи се и на простор који захватају улазни подаци. Када се говори о потребном меморијском простору не рачунајући простор који захватају улазни подаци, онда се говори о додатној просторној сложености.
Иако конкретно време извршавања зависи од рачунара и система на ком се програм извршава, релевантне процене утрошеног времена могу се дати разматрајући само алгоритам који се користи. Лош алгоритам за неки тежак проблем практично је неупотребљив чак иако би се користили рачунари који су за неколико редова величина ефикаснији него ови данашњи. Уместо о ефикасности програма обично се говори о сложености алгоритама. Ови термини користе се синонимно: алгоритми велике сложености доводе до неефикасних програма, док алгоритми мале сложености доводе до ефикасних програма.
Задатак програмера је често да направи баланс између потрошње различитих врста ресурса. Неки програми захтевају више меморије како би се брже извршавали. На пример, ако један програм врши потребно израчунавање за 10 секунди, а други за два и по минута, јасно је да је први програм практично примењивији. Међутим, ако први програм за своје извршавање захтева преко 10 гигабајта меморије, други око 1 гигабајт, а ми имамо рачунар са 4 гигабајта меморије, први програм нам је практично неупотребљив (иако ради много брже од другог). Ипак, с обзиром на то да савремени рачунарски системи имају прилично велику количину меморије (десетине гигабајта), време је ограничавајући фактор чешће него меморија и у наставку ћемо се више бавити анализом временске него меморијске сложености алгоритама. Са друге стране, треба имати у виду да се програми извршавају и на неким специјализованим платформама (уређајима са уграђеним рачунаром) и да је могуће да они имају много мање меморије него класични рачунари и мобилни уређаји, па ни просторну сложеност не треба занемарити.
Колико брзо програм треба да ради да бисмо га сматрали ефикасним зависи од конкретне примене. На пример, ако програм успе да за пола дана реши неки до тада нерешен математички проблем, који људи годинама нису могли да реше, он је свакако користан и можемо га сматрати веома ефикасним. Са друге стране, ако програм уграђен у аутомобил контролише кочнице приликом проклизавања, њему и неколико стотинки за израчунавање може бити превише, јер за то време аутомобил може да неконтролисано слети са пута.
Код програма који обрађују само мале количине података, временска и просторна сложеност нису много важне (јер се такви задаци извршавају брзо чак и ако се користе наивни алгоритми, и не захтевају много меморије). Међутим, у многим ситуацијама се сасвим природно јавља потреба за обрадом великих количина података и тада су неефикасни програми практично неупотребљиви (на пример, дигитална слика величине хиљаду пута хиљаду пиксела садржи милион пиксела, па сви алгоритми обраде слика баратају са огромном количином података и морају користити веома ефикасне алгоритме).
Иако су спори, наивни програми практично неупотребљиви, у развоју софтвера, посебно у неким областима, понекад се препоручује да је пожељно прво креирати најједноставнији програм који обавља дати задатак, а онда га модификовати ако је потребно да се уклопи у задата временска или просторна ограничења. Наиме, наивни алгоритми се често једноставно имплементирају, лако се разумеју и њихова исправност се лако доказује, а током њихове имплементације програмер може стећи неке увиде о проблему који се решава, добити идеје за ефикаснија решења, генерисати тестове за тестирање ефикаснијих решења, увидети да се неки делови кода јако ретко извршавају (па нема потребе губити време на њихову оптимзацију) и слично.
Оцена потребних ресурса се обично врши:
У неким ситуацијама нас занима понашање програма за конкретне улазне податке које имамо задатак да обрадимо на конкретном рачунару и тада се анализа програма може извршити и експериментално, покретањем програма и мерењем утрошених ресурса.
Најједноставнија мера временске ефикасности програма (или неког његовог дела) је његово време извршавања за неке конкретне вредности на конкретном рачунару.
У језику C++, погодан начин за мерење утрошеног времена пружају функције декларисане у заглављу <chrono>. Наредни пример илуструје како се може добити утрошено време изражено у микросекундама1. Овако добијено време није време утрошено за текући процес него апсолутно време које је протекло узмеђу два мерења. Ако је време извршавања функције кратко, саветује се да се оно измери више пута, па да се израчуна просечно утрошено време.
#include <iostream>
#include <chrono>
using namespace std;
void f(void) { ... }
int main() {
const int BROJ_POZIVA = 1000;
auto pocetak = chrono::high_resolution_clock::now();
for (int i = 0; i < BROJ_POZIVA; i++)
f();
auto kraj = chrono::high_resolution_clock::now();
auto trajanje =
chrono::duration_cast<chrono::microseconds>(kraj-pocetak);
cout << "Procena vremena rada jednog poziva funkcije f: "
<< trajanje.count() / BROJ_POZIVA << " mikrosekundi"
<< endl;
return 0;
}Постоје и друге функције које се користе за мерење утрошеног времена. У програмима на програмском језику C++, мерење времена може да се врши и коришћењем функција из језика C.
Када се установи да неки већи програм захтева превише времена, поставља се питање шта је тачно узрок томе, односно који део програма троши највише времена и треба да се оптимизује. Информације овог типа нам дају профајлери (енгл. profiler). Њихова основна улога је да пруже податке о томе колико пута је која функција позвана током (неког конкретног) извршавања, колико је утрошила времена и слично. Уколико се развијени програм не извршава жељено брзо, потребно је унапредити неке његове делове. Први кандидати за измену су делови који троше највише времена.
За оперативни систем Linux, популаран је систем valgring који обједињује мноштво алатки за динамичку анализу рада програма, укључујући профајлер callgrind. Профајлер callgrind се позива на следећи начин:
valgring --tool=callgrind mojprogram argumenti
где mojprogram означава извршиви програм који се анализира, а argumenti његове аргументе (командне линије). Програм callgrind извршава задати програм mojprogram са аргументима argumenti и региструје информације о томе која функција је позивала које функције (укључујући системске функције и функције из стандардне библиотеке), колико је која функција утрошила времена итд. Детаљнији подаци могу се добити ако је програм преведен у дебаг режиму (gcc компилатором, дебаг верзија се добија коришћењем опције -g). Прикупљене информације програм callgrind чува у датотеци са именом, на пример, callgrind.out.4873. Ове податке може да на прегледан начин прикаже, на пример, програм kcachegrind:
kcachegrind callgrind.out.4873
Слика 3 илуструје рад програма kcachegrind. Увидом у приказане податке, програмер може да уочи функције које троше највише времена и да покуша да их унапреди и слично.
Мање прецизан, али доста бржи је профајлер gprof.
За мерење утрошене количине меморије могу се користити програми memcheck и massif, који су такође део система valgrind.
Време извршавања програма или неких његових делова на неком конкретном рачунару може и да се процени, на основу анализе текста програма тј. операција које програм извршава. На такву процене утичу процене времена извршавања поједачних операција, али и оперативни система под којим рачунар ради, брзина улазно-излазних хардверских уређаја (на пример, диска) ако им програм приступа, од језика и од компилатора којим је направљен извршиви програм за тестирање, итд. На пример, на једном данашњем просечном рачунару, који ради под оперативним системом Linux, операција множења две вредности типа int троши око једну наносекунду тј. за једну секунду се на том рачунару може извршити око милијарду множења целих бројева. Процене времена извршавања програма може да пружи грубу слику о трајању извршавања програма, али треба их узимати са резервом, јер можда не узимају у обзир све процесе који се одигравају током извршавања програма, као ни оптимизације које су примењене у креирању извршивог програма. Ипак, процене су јако важне, јер програмер и пре писања кода треба да има неки груби осећај колико ресурса ће програм трошити и да ли ће одабрани алгоритам бити довољно ефикасан.
Понашање програма (па и количина утрошених ресурса), наравно, зависи од његових улазних параметара. Јасно је, на пример, да ће програм брже израчунати просечну оцену двадесетак ученика једног одељења, него просечну оцену неколико десетина хиљада ученика који полажу државну матуру.
За величину улаза може се узети број улазних елемената које треба обрадити (на пример, дужина низа) или број битова потребних за записивање улаза или вредност елемената које треба обрадити. Да би се избегла забуна, увек је потребно експлицитно навести у односу на коју величину улазне вредности се разматра сложеност.
Понашање програма често зависи само од укупне количине података а не и од конкретних вредности које обрађује. У наведеном примеру, понашање програма зависи само од броја ученика, а не и од конкретних оцена које су ученици добили. Зато сложеност алгоритма често изражавамо у функцији величине (димензије) његових улазних параметара, а не самих вредности параметара.
Многи алгоритми се не извршавају исто за све улазе исте величине, па је потребно наћи начин за описивање ефикасности алгоритма за разне могуће улазе исте величине.
Анализа најгорег случаја заснива процену сложености алгоритма на најгорем случају (на случају за који се алгоритам најдуже извршава –- у анализи временске сложености, или на случају за који алгоритам користи највише меморије –- у анализи просторне сложености). Та процена може да буде варљива, тј. превише песимистична. На пример, ако се програм у 99,9% случајева извршава испод секунде, док се само у 0,1% случајева извршава за 10 секунди, анализа најгорег случаја даје закључак само о извршавању за 10 секунди. Са друге стране, анализа најгорег случаја нам даје гаранције да ако је програм у најгорем случају довољно ефикасан, онда у свим могућим случајевима може да се изврши са расположивим ресурсима. Анализа најгорег случаја је најчешћи облик изражавања сложености алгоритма и ако се не нагласи другачије, под сложеношћу алгоритма се подразумева управо сложеност најгорег случаја.
У неким ситуацијама могуће је извршити анализу просечног случаја и израчунати просечно време извршавања алгоритма, али да би се то урадило, потребно је познавати простор допуштених улазних вредности и вероватноћу да се свака допуштена улазна вредност појави на улазу програма. У случајевима када је битна гаранција ефикасности сваког појединачног извршавања програма, процена просечног случаја може бити варљива, превише оптимистична, и може да се деси да у неким ситуацијама програм не може да се изврши са расположивим ресурсима. На пример, анализа просечног случаја би за поменути програм пријавила да се у просеку извршава испод једне секунде, међутим, за неке улазе он се може извршавати и преко десет секунди.
Анализа најбољег случаја је превише оптимистична и најчешће нема смисла. Њено познавање може бити корисно као познавање доње границе извршавања.
Некада се анализа врши тако да се процени укупно време потребно да се изврши одређен број сродних операција. Тај облик анализе назива се амортизована анализа и у тим ситуацијама нам није битно време извршавања појединачних операција, већ само збирно време извршавања свих операција. Овај облик анализе је посебно погодан у случајевима када време извршавања појединачних операција у некој серији операција може да варира и када се дешава да време потрошено за неко извршавање операције омогућава да наредних неколико извршавања те операције буде веома брзо. Типичан пример је додавање елемената на крај низа који се динамички шири (операција push_back на векторима у језику C++). Приликом првог додавања елемената алоцира се одређена количина меморије (што је временски захтевно), да би се у наредним операцијама елементи само уписивали у раније алоцирану меморију (што је временски веома ефикасно). Када се алоцирани простор попуни, пре додавања елемента потребно је реалоцирати меморију што је поново временски захтевно. Ако се обезбеди да се проширивање низа и реалокација меморије дешавају довољно ретко, овакве структуре података имају ниску амортизовану сложеност.
Временска и просторна сложеност алгоритма одређују његову практичну употребљивост тј. највеће улазне вредности за које је могуће да ће се алгоритам извршити у неком разумном времену.
Нека је функција \(T(n)\) представља меру времена потребног за извршавање алгоритма за улаз величине \(n\) (у најгорем случају, ако се не нагласи другачије). Под претпоставком да се свака инструкција извршава приближно исто време, ова функција може се добити и на основу функције којом се изражава број инструкција које алгоритам извршава за улаз величине \(n\).
У анализи многих алгоритама, функција \(T(n)\) изражава се као нека комбинација логаритамске функције \(\log(n)\), корене функције \(\sqrt{n}\), полиномских функција \(n\), \(n^2\), \(n^3\), \(\ldots\), експоненцијалних функција \(2^n\), \(3^n\), \(\ldots\), факторијелне функције \(n!\) и слично. Њихова основна математичка својства (пре свега брзина раста) резимирани су у додатку @sec:elementarne_asimptotski.
Табела 1 приказује потребно време извршавања алгоритма ако се претпостави да једна инструкција траје једну наносекунду (\(10^{-9}\) секунди). Ова процена је груба, али није превише погрешна и даје добру процену реалних времена на данашњим рачунарима.
| \(n / T(n)\) | \(\log{n}\) | \(\sqrt{n}\) | \(n\) | \(n\log{n}\) | \(n^2\) | \(n^3\) |
|---|---|---|---|---|---|---|
| \(10\) | 0,003 \(\mu\)s | 0,003 \(\mu s\) | 0,01 \(\mu\)s | 0,033 \(\mu\)s | 0,1 \(\mu\)s | 1 s |
| \(100\) | 0,007 \(\mu\)s | 0,010 \(\mu s\) | 0,1 \(\mu\)s | 0,644 \(\mu\)s | 10 \(\mu\)s | 1 ms |
| \(1\,000\) | 0,010 \(\mu\)s | 0,032 \(\mu s\) | 1,0 \(\mu\)s | 9,966 \(\mu\)s | 1 ms | 1 s |
| \(10\,000\) | 0,013 \(\mu\)s | 0,1 \(\mu s\) | 10 \(\mu\)s | 130 \(\mu\)s | 0,1 s | 16,7 min |
| \(100\,000\) | 0,017 \(\mu\)s | 0,316 \(\mu s\) | 100 \(\mu\)s | 1,67 ms | 10 s | 11,57 dan |
| \(1\,000\,000\) | 0,020 \(\mu\)s | 1 \(\mu s\) | 1 ms | 19,93 ms | 16,7 min | 31,7 god |
| \(10\,000\,000\) | 0,023 \(\mu\)s | 3,16 \(\mu s\) | 10 ms | 0,23 s | 1,16 dan | \(3\times 10^5\) god |
| \(100\,000\,000\) | 0,027 \(\mu\)s | 10 \(\mu s\) | 0,1 s | 2,66 s | 115,7 dan | |
| \(1\,000\,000\,000\) | 0,030 \(\mu\)s | 31,62 \(\mu s\) | 1 s | 29,9 s | 31,7 god |
У наредном примеру је илустровано како су вредности у овој табели израчунате.
Пример 2.2.1. Нека је \(n=10\,000\) и \(T(n)=n^2\). Број извршених инструкција је онда \(T(n)=T(10\,000)=10\,000^2=(10^4)^2 = 10^8\), а време је \(10^8 \cdot 10^{-9}\mathrm{s} = 0,1 \mathrm{s}\).
Нека је \(n=1\,000\,000=10^6\) и \(T(n)=n\log_2{n}\). Важи да је \(\log_2(10^6) = 2\log_2(10^3) \approx 20\) (јер је \(2^{10}=1024\approx 1000\)). Зато је \(T(n)=10^6\cdot 20 = 2\cdot 10^7\), а време је приближно једнако \(2\cdot 10^7\cdot 10^{-9}\mathrm{s} =20\cdot 10^{-3} s =20 \mathrm{ms}\).
Алгоритми чија је сложеност одоздо ограничена експоненцијалном или факторијелском функцијом се сматрају неефикасним.
| \(n / T(n)\) | \(2^n\) | \(n!\) |
|---|---|---|
| 10 | 1 \(\mu\)s | 3,63 ms |
| 20 | 1 \(ms\) | 77,1 god |
| 30 | 1 \(s\) | \(8,4\times 10^{15}\) god |
| 40 | 18,3 min | |
| 50 | 13 dan | |
| 100 | \(4 \times 10^{13}\) god |
Можемо поставити и питање која димензија улаза се отприлике може обрадити за одређено време. Одговор је дат у наредној табели.
| \(t\) | \(n\) | \(n\log{n}\) | \(n^2\) | \(n^3\) | \(2^n\) | \(n!\) |
|---|---|---|---|---|---|---|
| 1 ms | \(10^6\) | \(63\,000\) | \(1\,000\) | \(100\) | \(20\) | \(9\) |
| 10 ms | \(10\cdot 10^6\) | \(530\,000\) | \(3\,200\) | \(215\) | \(23\) | \(10\) |
| 100 ms | \(100\cdot 10^6\) | \(4,5\cdot 10^6\) | \(10\,000\) | \(465\) | \(27\) | \(11\) |
| 1 s | \(10^9\) | \(40\cdot 10^6\) | \(32\,000\) | \(1\,000\) | \(30\) | \(12\) |
| 1 min | \(60\cdot 10^{9}\) | \(1,9\cdot 10^9\) | \(245\,000\) | \(3\,900\) | \(36\) | \(14\) |
Покушајмо сада да податке из датих табела представимо графички (слика 4). Услед јако велике разлике у брзинама раста анализираћемо само “суседне” функције.
На првом графику на слици 4 приказан је однос времена извршавања експоненцијалних и полиномских алгоритама. Већ за димензију 30 експоненцијални алгоритам захтева око једне секунде, док је време извршавања алгоритама полиномске сложености практично занемариво (чак и у случају полинома већег степена, попут \(n^3\)).
На другом графику приказан је однос брзина раста полиномских алгоритама. Повећањем степена прати јако велики пораст времена. Алгоритам који захтева \(n^3\) инструкција је много спорији него онај који захтева \(n^2\) инструкција (кубном је већ за проблем димензије око \(1\,000\) потребно око једне секунде, док квадратни и линеарни на тим димензијама посао обављају практично моментално).
На трећем графику приказан је однос три функције веома честе у анализи алгоритама: \(n^2\), \(n \log{n}\) и \(n\). Са графика се може уочити да на димензијама на којима су квадратном алгоритму потребне већ секунде, нема велике разлике између алгоритама којима је потребно \(n \log{n}\) и \(n\) инструкција – оба скоро тренутно завршавају посао.
Да би се разлика између таквих алгоритама опазила, потребно је да се димензија улаза знатно повећа, што је и приказано на четвртом графику. Тек када димензија улаза достигне милионе, види се да је алгоритам који захтева \(n \log{n}\) инструкција нешто спорији. Са графика се види да својим обликом та функција јако личи на линеарну (отуда и назив “квазилинеарна” функција). Са графика се може видети и да разлика између линеарне и квазилинеарне функције није “драстична”, јер се повећавањем константног фактора уз линеарну функцију (фактора \(25\) на овом графику) може десити да на улазима разматране димензије број корака буде већи него код основне квазилинеарне функције.
На петом графику се види да је време извршавања алгоритама код којих број корака логаритамски зависи од димензије улаза практично занемариво (чак и за огромне улазе од милијарду елемената). Треба имати на уму да је само за учитавање толиког улаза потребно линеарно време, па предност алгоритама логаритамске сложености долази тек код проблема код којих се након учитавања подаци обрађују велики број пута или код алгоритама код којих нема потребе за учитавањем свих података.
Закључак који следи из проучавања приказаних графика је да измена алгоритма таква да се број корака уместо неком функцијом из нашег разматраног низа функција изражава претходном у том низу, доноси драстично смањење времена извршавања и могућност обраде много већих улаза. Изузетак делом представљају функције \(n \log{n}\) и \(n\), које су веома блиске и њихова разлика долази до изражаја тек код јако великих улаза (ово је јасно када се погледа количник сваке две суседне функције – код ове две функције он је убедљиво најмањи).
Природно се поставља питање шта ако функција \(T(n)\) која одређује зависност између броја потребних корака тј. времена израчунавања и димензије улаза није овако једноставна.
Пример 2.2.2. На пример, нека је \(T(n)=2n^2 + 10n + 8\)? Колико је време потребно за \(n=10^5\)? Број потребних корака је \(2\cdot (10^5)^2 + 10\cdot 10^5 + 8\), а потребно време је \(2\cdot 10^{10}\cdot 10^{-9}\mathrm{s} + 10 \cdot 10^5\cdot 10^{-9}\mathrm{s} + 8\cdot 10^{-9}\mathrm{s} = 20\mathrm{s} + 1\mathrm{ms} + 8\mathrm{ns} \approx 20\mathrm{s}\). Дакле, фактор \(2n^2\) даје време \(20\mathrm{s}\), фактор \(10n\) даје време \(1\mathrm{ms}\), а фактор \(8\) даје време \(8\mathrm{ns}\). Очигледно је да је удео времена које долази од чланова \(10n\) и \(8\) занемарив у укупном збиру. Нема, дакле, за велике вредности \(n\) никакве значајне разлике између функција \(T(n)=2n^2\), \(T(n)=2n^2+10n+8\), па чак ни \(T(n) = 2n^2 + 1000n + 5000\).
Дакле, време извршавања алгоритма је за велике улазе практично потпуно одређено доминантним чланом у функцији која описује зависност броја корака од димензије улаза.
Још једно питање које се намеће је колико је значајан водећи коефицијент уз тај доминантни члан.
Пример 2.2.3. Видели смо да нема практично никакве разлике између \(2n^2 + 10n + 8\) и \(2n^2\). Између \(n^2\), \(2n^2\) и \(5n^2\) разлике има, али је она много мање значајна од разлике између, на пример, \(n^2\) и \(1000n\). Наиме, већ за \(n > 1000\) алгоритам који захтева \(n^2\) корака ће бити спорији од оног који захтева \(1000 n\) корака и та разлика ће се повећавати са порастом \(n\). За \(n=10^6\), први алгоритам ће бити 1000 пута спорији него други drugi.
Дакле, ред величине водећег члана је много значајнији за опис ефикасности (за велике вредности \(n\)) него што је коефицијент уз водећи члан. Разлика између, на пример, \(2n^2\) и \(5n^2\) се може надоместити неким мањим оптимизацијама или бољим хардвером, док се разлика између \(n^2\) и \(n\) не може никако надоместити осим заменом алгоритма.
Видели смо да нам је приликом анализе сложености алгоритама потребно да грубо проценимо брзину раста функција које описују зависност потребног времена и меморије у односу на величину улаза, тј. само да одредимо доминантни члан те функције, занемарујући остале чланове и коефицијент уз доминантни члан. Таква груба процена нам може дати информацију о томе да ли се за неку величину улаза време мери милисекундама, секундама, сатима, данима, годинама итд. Математичке ознаке \(O\), \(\Omega\) и \(\Theta\) користе се да би се описала брзина раста функција2.
Размотримо како можемо дефинисати појам \(f(n)=O(g(n))\). Желимо да искажемо да ће почевши од неке величине улаза вредности функције \(f\) бити мање од вредности функције \(g\). Пошто желимо да занемаримо вредност водећег коефицијента испред доминантног члана, допустићемо да се функција \(g\) скалира произвољном константном \(c\) тј. да се допусти да вредности функције \(f\) буду мање од вредности функције \(c\cdot g\). Такође, пошто нас однос функција \(f\) и \(c\cdot g\) занима само за велике вредности \(n\), захтеваћемо да важи \(f(n) \leq c \cdot g(n)\) за довољно велике вредности \(n\), тј. за свако \(n\) веће од неке произвољне вредности \(n_0\). Дакле, појам \(f(n)=O(g(n))\) се формално може дефинисати на следећи начин.
Дефиниција 2.2.1. Ако постоје позитивна реална константа \(c\) и природан број \(n_0\) такви да за функције \(f\) и \(g\) над природним бројевима важи
\[f(n) \leq c \cdot g(n),\]
за сваки природан број \(n\) већи од \(n_0\) онда пишемо \(f(n)=O(g(n))\) и читамо “\(f\) је велико о од \(g\)”.
Нагласимо да \(O(g(n))\) не означава неку конкретну функцију, већ класу функција и уобичајени запис \(f(n)=O(g(n))\) заправо значи \(f(n) \in O(g(n))\). Поред тога, како \(O\) представља релацију, однос између две задате функције \(f\) и \(g\), а не однос између њихових конкретних вредности, под записом \(f(n) \in O(g(n))\), заправо се мисли \(f \in O(g)\) (јер су \(f\) и \(g\) функције, а \(f(n)\) и \(g(n)\) њихове вредности).
Дефиниција 2.2.2. Ако је \(T(n)\) време извршавања алгоритма \(A\) (чији улаз карактерише природан број \(n\)) и ако важи \(T(n)=O(f(n))\), онда кажемо да је алгоритам \(A\) сложености или реда \(O(f(n))\) или да алгоритам \(A\) припада класи \(O(f(n))\).
Пример 2.2.4. Може се доказати да важи:
Теорема 2.2.1. Релација \(O\) има следећа својства.
Ако су \(a\) и \(b\) реални бројеви и \(a>0\), онда важи \(a f(n)+b = O(f(n))\) (тј. мултипликативне и адитивне константе не утичу на класу којој функција припада).
Ако важи \(f_1(n) = O(g_1(n) )\) и \(f_2(n) = O(g_2(n) )\), онда важи и \(f_1(n) +f_2(n) = O(g_1(n) +g_2(n) )\) и \(f_1(n) \cdot f_2(n) = O(g_1(n) \cdot g_2(n) )\).
Релације \(\Omega\) и \(\Theta\) се дефинишу слично релацији \(O\).
Дефиниција 2.2.3. Ако постоје позитивна реална константа \(c\) и природан број \(n_0\) такви да за функције \(f\) и \(g\) над природним бројевима важи
\[c \cdot g(n) \leq f(n),\]
за сваки природан број \(n\) већи од \(n_0\), онда пишемо \(f(n)=\Omega(g(n))\) и читамо “\(f\) је велико omega од \(g\)”.
Дефиниција 2.2.4. Ако постоје позитивне реалне константе \(c_1\) и \(c_2\) и природан број \(n_0\) такви да за функције \(f\) и \(g\) над природним бројевима важи
\[c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n),\]
за сваки природан број \(n\) већи од \(n_0\), онда пишемо \(f(n)=\Theta(g(n))\) и читамо “\(f\) је велико тета од \(g\)”.
Аналогно дефиницији 2.2.2 дефинише се када алгоритам \(A\) припада класи \(\Omega(g(n))\) и када припада класи \(\Theta(g(n))\). Сложеност алгоритама најчешће се изражава у терминима \(O\) (што важи и за наставак ове књиге).
Појмови велико о (\(O\)), велико омега (\(\Omega\)) и велико тета (\(\Theta\)) илустровани су на слици 5.
Пример 2.2.5. Може се доказати да важи:
\(5 \cdot 2^n+9 = \Theta(2^n)\)
За \(c_1=5\), важи \(c_1 \cdot 2^n \leq 5 \cdot 2^n+9\) за све вредности \(n\) веће од \(0\). За \(c_2=6\), важи \(5 \cdot 2^n+9 \leq c_2 2^n\) за све вредности \(n\) веће од \(3\). Из наведена два тврђења следи задато тврђење.
\(2^n+2^n n = \Theta(2^n n)\)
За \(c_1=1\), важи \(c_1 \cdot 2^n n \leq 2^n+2^n n\) за све вредности \(n\) веће од \(0\). За \(c_2=2\), важи \(2^n+2^n n \leq c_2 2^n n\) за све вредности \(n\) веће од \(0\). Из наведена два тврђења следи задато тврђење.
Теорема 2.2.2. Релацијe \(O\), \(\Omega\) и \(\Theta\) имају следећа својства.
Информација о сложености алгоритма у терминима \(\Theta\) (која даје и горњу и доњу границу) прецизнија је него информација у терминима \(O\) (која даје само горњу границу) или информација у терминима \(\Omega\) (која даје само доњу границу). Међутим, обично је сложеност алгоритма једноставније исказати у терминима \(O\) него у терминима \(\Theta\). Штавише, за неке алгоритме сложеност се не може лако исказати у терминима \(\Theta\). На пример, ако за неке улазе алгоритам троши \(n\), а за неке \(n^2\) временских јединица, за тај алгоритам се не може рећи ни да је реда \(\Theta(n)\) ни реда \(\Theta(n^2)\), али јесте реда \(O(n^2)\) (па и, на пример, реда \(O(n^3)\)). Када се каже да алгоритам припада класи \(O(g(n))\) обично се подразумева да је \(g\) најмања таква класа (или макар — најмања за коју се то може доказати). И \(O\) и \(\Theta\) нотација се користе и у анализи најгорег случаја и у анализи просечног случаја.
Сложеност алгоритама у терминима \(\Omega\) разматра се ређе него сложеност у терминима \(\Theta\) и \(O\), али понекад такође може да буде веома важна. Сложеност у терминима \(O\) даје горњу границу за неку функцију, а сложеност у терминима \(\Omega\) даје доњу границу. То се може разумети и овако: сложеност у терминима \(O\) говори нам колико је неки алгоритам добар (“асимптотски није лошији него…”), а сложеност у терминима \(\Omega\) говори нам колико је неки алгоритам лош (“асимптотски није бољи него…”). На пример, може се показати да је просечно време извршавања неког алгоритма за сортирање реда \(\Omega(n^2)\) и то говори да је тај алгоритам лош (јер постоје алгоритми чије време извршавање припада класи \(O(n \log n)\).
Лако се доказује да функција која је константна (колико год да је та константа велика) припада класама \(O(1)\), \(\Omega(1)\) и \(\Theta(1)\). Штавише, свака функција која је ограничена одозго неком константом припада класама \(O(1)\) и \(\Theta(1)\).
За алгоритме сложености \(O(1)\) кажемо да имају константну сложеност, за алгоритме сложености \(O(n)\) кажемо да имају линеарну, за \(O(n\log{n})\) да имају квазилинеарну, за \(O(n^2)\) квадратну, за \(O(n^3)\) кубну, за \(O(n^k)\) за неко \(k\) полиномску (негде се каже и полиномијалну), за \(O(a^n)\) за неко \(a\) експоненцијалну, а за \(O(\log n)\) логаритамску сложеност.
Природа параметра класе сложености зависи од самог алгоритма. Сложеност израчунавања неке функције може да зависи и од више параметара: на пример, класа \(O(n)\) има параметар \(n\), док класа \(O(2^{m+k})\) има параметре \(m\) и \(k\). На пример, алгоритам који за \(n\) улазних тачака проверава да ли припадају унутрашњости неког од \(m\) задатих троуглова, који комбинује сваку тачку са сваким троуглом, има сложеност \(O(mn)\). Сложеност функције која сабира два броја фиксне ширине је константна тј. припада класи \(O(1)\), а бројева произвољне ширине је \(O(m+n)\), где је \(m\) број цифара првог, а \(n\) број цифара другог броја. Пошто број цифара броја одговара величини улаза (тј. броју битова потребних за запис), сложеност сабирања је линеарна у односу на број битова потребних за запис улаза. Са друге стране, ако се сложеност изрази у односу на вредности бројева који се сабирају, она ће бити логаритамска (јер број цифара логаритамски зависи од величине бројева). Као што је већ речено, потребно је увек експлицитно навести у односу на коју величину или које величине се разматра сложеност алгоритма.
Сложеност израчунавања је изузетно важна и из практичне и из теоријске перспективе. Класа сложености \(P\) је класа проблема за које постоје алгоритми који су полиномске сложености (у односу на улазну величину). Проблем САТ (од енглеског satisfiability) је проблем испитивања задовољивости исказне формуле у конјунктивној нормалној форми — за улазну формулу треба дати одговор да ако је формула задовољива, а одговор не иначе. Тренутно није познато да ли за овај проблем постоји решење које ради у полиномском времену у односу на дужину задате формуле. Ниједан тренутно познат алгоритам за САТ нема полиномску сложеност, сви имају експоненцијалну сложеност. Питање да ли САТ припада класи \(P\) једно је од најважнијих отворених питања у рачунарству. Поред класе \(P\), изучавају се и многе друге класе проблема и алгоритама на основу њихове просторне и временске сложености.
Одређивање (временске и просторне) сложености алгоритама заснива се на одређивању функције \(T(n)\) тј. одређивање тачног или приближног броја инструкција које се извршавају и меморијских јединица које се користе. Тачно одређивање тих вредности најчешће је веома тешко или немогуће, те се обично користе разна поједностављивања. На пример, често се сматра да све појединачне инструкције (осим позива функција) троше једнако времена. Оно што је важно је да таква поједностављивања не утичу на класу сложености којој алгоритам припада (јер, као што је речено, константни адитивни и мултипликативни фактори не утичу на ред алгоритма).
Уколико се део програма састоји од неколико инструкција без гранања и петљи, онда се процењује да је његово време извршавања увек исто, константно, те да припада класи \(O(1)\).
Уколико програм има два дела, временске сложености3 \(O(f)\) и \(O(g)\), који се извршавају један за другим, укупна сложеност је4 \(O(f+g)\).
То важи и у случају када се у тим деловима јављају рекурзивни позиви (тада, на пример, временска сложеност изражена у терминима вредности \(f(n)\) може да зависи од временске сложености изражене у терминима вредности \(f(n-1)\)), али тада ефективно израчунавање сложености захтева коришћење додатних техника (видети поглавље 2.2.3).
Уколико део програма садржи једно гранање и уколико време извршавања једне гране припада класи \(O(f)\) а друге гране припада класи \(O(g)\), онда је укупно време извршавања тог дела програма ограничено временом које захтева сложенија грана, па припада класи \(O(\max(f, g))\), а она је једнака класи \(O(f + g)\).
Уколико део програма садржи петљу која се извршава \(n\) пута, а време извршавања тела петље је константно, онда укупно време извршавања тог дела програма припада класи \(O(n)\).
Уколико део програма садржи петљу која се извршава за вредности \(i\) од \(1\) до \(n\), а време извршавања тела петље је \(O(f(i))\), онда укупно време извршавања тог дела програма припада класи \(O(f(1)+f(2)+\ldots+f(n))\).
Уколико део програма садржи двоструку петљу – једну која се извршава \(m\) пута и, унутар ње, другу која се извршава \(n\) пута и уколико је време извршавања тела унутрашње петље константно, онда укупно време извршавања тог дела програма припада класи \(O(m \cdot n)\). Ова правила могу се даље уопштити.
Аналогно се рачуна временска сложеност за друге врсте комбиновања линеарног кода, гранања и петљи.
Анализа просторне сложености се врши слично.
Уколико део програма не садржи позиве функција, динамичку алокацију, нити декларације објеката чија величина зависи од неких параметера, онда је просторна сложеност тог дела програма константа тј. припада класи \(O(1)\).
Уколико неки део програма врши динамичку алокацију неких \(n\) објеката величине \(O(1)\) – онда то доприноси његовој просторној сложености \(O(n)\).
Уколико програм има два дела, просторне сложености \(O(f)\) и \(O(g)\), који се извршавају један за другим, укупна сложеност је \(O(f+g)\).5
Уколико се у програму јављају позиви функција, сваки позив заузима неки фиксни простор на програмском стеку (величина тог простора може бити ограничена једном константом заједничком за све функције) као и додатни простор који заузимају локалне променљиве те функције (које заузимају простор на позивном стеку или су делом, као на пример, елементи вектора, смештени у хипу).
Уколико се јављају рекурзивни позиви, онда у просторну сложеност улази максимални број стек оквира који се могу наћи на програмском стеку током извршавања и чија је величина константна,6 али и елементи локалних променљивих који се чувају у хип сегменту.
Уколико део програма просторне сложености \(O(f)\) позива функцију просторне сложености \(O(g)\), онда укупна просторна сложеност тог дела програма припада класи \(O(f + g)\). Аналогно се рачуна просторна сложеност за друге врсте комбиновања кода.
Прикажимо сада кроз неколико примера анализу сложености итеративно имплементираних алгоритама. Да би могла да се анализира сложеност програма потребно је владати одређеним математичким апаратом (на пример, израчунавањем или проценом одређених сума, постављањем и решавањем рекурентних једначина и слично). Неке математичке технике које су потребне за анализу сложености резимиране су у додатку @sec:matematika.
Пример 2.2.6. Израчунајмо временску сложеност наредне функције која исписује троугаони део таблице множења:
void mnozenje(int n)
{
int i, j;
if (n == 0)
return;
else {
for (i = 1; i <= n; i++) {
for (j = i; j <= n; j++)
cout << i << "*" << j << " = " << i*j << "\t";
cout << endl;
}
}
}За n једнако \(5\), функција даје излаз:
1*1 = 1 1*2 = 2 1*3 = 3 1*4 = 4 1*5 = 5 2*2 = 4 2*3 = 6 2*4 = 8 2*5 = 10 3*3 = 9 3*4 = 12 3*5 = 15 4*4 = 16 4*5 = 20 5*5 = 25
Сматраћемо да се тело унутрашње петље у else грани извршава константно време \(c\). Унутрашња петља има \(n-i+1\) итерација, те је њено време извршавања \((n-i+1)c\). Спољашња петља има \(n\) итерација, а \(i\)-та итерација има време извршавања \((n-i+1)c\). Укупно време извршавања спољашње петље је
\[\sum_{i=1}^n (n-i+1)c = \sum_{i=1}^n ic = \frac{n(n+1)c}{2}.\]
Грана if извршава се константно време \(c'\), па је укупна сложеност функције mnozenje \(O\left(c' + \frac{n(n+1)c}{2}\right) = O(n(n+1)) = O(n^2)\).
Функција mnozenje нема позива других функција и не користи динамичку алокацију, нити објекте чија величина зависи од улазних параметара, те је њена просторна сложеност константна, тј. припада реду \(O(1)\).
У наредним примерима ћемо се потрудити да покријемо облике петљи који се јављају у великом броју конкретних алгоритама и решења конкретних задатака. У примерима петљи који следе, претпоставља се да кôд у телу петљи који није приказан не утиче на бројачке променљиве и не мења границе петљи. За разлику од претходног задатка нећемо детаљно израчунавати број инструкција, већ ћемо га само процењивати на основу облика петљи.
Пример 2.2.7. Размотримо неколико честих облика петље for.
for (int i = 0; i < n; i++)
// kod slozenosti O(1)Сложеност претходне петље је \(O(n)\).
for (int i = m; i < n; i++)
// kod slozenosti O(1)Сложеност претходне петље је \(O(n-m)\).
for (int i = 0; i < n; i += 2)
// kod slozenosti O(1)Сложеност претходне петље је \(O(n)\). Пошто се петља извршава за парне вредности бројачке променљиве, тело петље се извршава око \(\frac{n}{2}\) пута и константни фактор је \(\frac{1}{2}\), али је сложеност и даље линеарна.
for (int i = 0, j = n-1; i < j; i++, j--)
// kod slozenosti O(1)Сложеност претходне петље је \(O(n)\). Показивачи се сусрећу приближно на средини опсега, а тело петље се извршава око \(\frac{n}{2}\) пута.
Могло би се помислити да је сложеност сваке петље линеарна, али то није увек случај.
for (int i = 0; i < 10; i++)
// kod slozenosti O(1)Сложеност претходног кода је \(O(1)\). Иако је присутна петља, број њених извршавања је увек 10 и не зависи ни од једног параметара, па га можемо сматрати малом константом.
for (int i = 1; i*i <= n; i++)
// kod slozenosti O(1)Иако садржи једну петљу, сложеност претходног кода није \(O(n)\), већ \(O(\sqrt{n})\). Наиме, петља се извршава све док је \(i^2 \leq n\) тј. док је \(i \leq \sqrt{n}\).
for (int i = 1; i < n; i *= 2)
// kod slozenosti O(1)Иако претходни код садржи петљу, његова сложеност је \(O(\log{n})\), јер се вредност променљиве i дуплира у сваком кораку, све док не престигне граничну вредност \(n\).
Пример 2.2.8. Размотримо сада примере програма у којима се јавља неколико петљи.
for (int i = 0; i < m; i++)
// kod slozenosti O(1)
for (int i = 0; i < n; i++)
// kod slozenosti O(1)Сложеност претходних петљи је \(O(m+n)\). Наиме, тело прве петља се изврши \(m\) пута, а затим тело друге петље \(n\) пута, па се тела обе петље укупно изврше \(m+n\) пута.
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
// kod slozenosti O(1)Сложеност претходних петљи је \(O(n^2)\). Заиста, спољашња петља се извршава \(n\), а у њеном телу се унутрашња петља извршава \(n\) пута, па се тело унутрашње петље изврши тачно \(n^2\) пута.
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
// kod slozenosti O(1)Сложеност претходних петљи је \(O(mn)\). Заиста, спољашња петља се извршава \(m\), а у њеном телу се унутрашња петља извршава \(n\) пута, па се тело унутрашње петље изврши тачно \(mn\) пута.
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
// kod slozenosti O(1)Сложеност претходних петљи је \(O(n^2)\). Број извршавања тела унутрашње петље је \((n-1) + (n-2) + \ldots + 2 + 1\), што је једнако \(\frac{n(n-1)}{2} = \frac{1}{2}n^2 - \frac{1}{2}n\). Константни фактор је \(\frac{1}{2}\), али је сложеност квадратна. До истог резултата можемо доћи ако схватимо да у сваком кораку унутрашње петље пар бројача одређује једну комбинацију бројева од \(0\) до \(n-1\). Зато број извршавања тела одговара броју двочланих комбинација скупа од \(n\) елемената, што је једнако \(\binom{n}{2} = \frac{n(n-1)}{2}\).
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
// kod slozenosti O(1)Сложеност претходних петљи је прилично очигледно \(O(n^3)\).
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
for (int k = j+1; k < n; k++)
// kod slozenosti O(1)Сложеност претходних петљи је \(O(n^3)\). Најлакши начин да се ово закључи је да се примети да сваком извршавању тела одговара једна трочлана комбинација елемената скупа \(0\), \(\ldots\), \(n-1\). Пошто трочланих комбинација има \(\binom{n}{3} = \frac{n(n-1)(n-2)}{3\cdot 2 \cdot 1}\), сложеност је кубна, а константни фактор је \(\frac{1}{6}\).
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
// kod slozenosti O(1)
for (int i = 0; i < n; i++)
// kod slozenosti O(1)Сложеност претходних петљи је \(O(n^2)\). Наиме, тело угнежђених петљи се изврши \(\frac{n(n-1)}{2}\) пута, а затим тело друге петље \(n\) пута, што је заправо занемариво мало у односу на број извршавања тела угнежђених петљи. Дакле, први део кода доминира временом извршавања и сложеност је \(O(n^2)\).
for (int i = 1; i <= n; i++)
for (int j = 1; j < i; j *= 2)
// kod slozenosti O(1)Сложеност претходног кода је \(O(n \log{n})\). Сложеност унутрашње петље, за свако конкретно i је \(O(\log{i})\), па је укупна сложеност отприлике једнака \(\log{1} + \log{2} + \ldots + \log{n}\), а за ово се може показати да је \(O(n \log{n})\) (јасно је да је израз мањи или једнак \(n \log{n}\) јер је сваки сабирак мањи или једнак \(\log{n}\), међутим, може се показати и да је збир већи или једнак од \(\frac{n}{2}\log{\frac{n}{2}}\) (што је такође \(\Theta(n \log{n})\)), занемаривањем првих \(\frac{n}{2}\) сабирака, након чега остају само сабирци који су већи или једнаки \(\log{\frac{n}{2}}\)).
for (int i = n; i >= 1; i /= 2)
for (int j = 1; j < i; j++)
// kod slozenosti O(1)Сложеност претходног кода је \(O(n)\). Наиме, број извршавања унутрашње петље је \(n + \frac{n}{2} + \frac{n}{4} + \ldots\), за шта се лако може показати да је одозго ограничено са \(2n\).
int j = 0;
for (int i = 0; i < n; i++) {
while (j < n && P[j]) {
// kod slozenosti O(1)
j++;
}
// kod slozenosti O(1)
}Иако постоје угнежђене петље, сложеност претходне петље је \(O(n)\). Кључни детаљ је то што унутрашња петља нема иницијализацију променљиве j на нулу и бројач ј у унутрашњој петљи се све време само увећава (исто као и бројач i у спољашњој петљи). Укупан број корака је стога ограничен са \(2n\).
int l = 0, d = n-1;
while (l < d) {
do l++; while (l < d && P(a[l]));
do d--; while (l < d && !P(a[d]));
if (l < d)
// kod slozenosti O(1)
}Сличан кôд се, на пример, може срести у алгоритму партиционисања низа тако да се елементи раздвоје на оне који не задовљавају својство P и на оне који задовољавају својство P. И претходни алгоритам је сложености \(O(n)\) иако и он садржи угнежђене петље. То поново можемо утврдити амортизованом анализом (јер не знамо појединачни број извршавања унутрашњих петљи, али можемо лако проценити укупан број корака који се у њима направи). Наиме, променљива l се само увећава кренувши од почетка, а d се само смањује кренувши од краја низа, док се не сусретну, што ће се десити у највише \(n\) корака.
Дакле, иако нам у већини случајева угнежђеност петљи описује сложеност алгоритма, треба бити обазрив и код анализирати пажљивије, да се сложеност не би преценила.
Често процену сложености грубо вршимо тако што анализирамо структуру петљи у програму, занемарући остале операције (обично за све сем петљи сматрамо да је \(O(1)\)). То може бити прилично варљиво, јер се у коду могу позивати функције (било кориснички дефинисане, било библиотечке) које нису константне сложености. Још горе, и неки оператори могу бити неконстантне сложености (обично линеарне).
string rez = "";
for (char c : s)
rez = c + rez;Иако има само једну петљу, претходни фрагмент може бити сложености \(O(n^2)\), где је \(n\) дужина ниске s. Наиме, додавање карактера на почетак ниске у језику C++ може бити линеарне сложености \(O(n)\), где је \(n\) дужина ниске (јер захтева померање наредних карактера надесно).
У наредном примеру анализирамо сложеност рекурзивно дефинисане функције (много више речи о овоме биће дато у делу уџбеника посвећеном рекурзивним приступима решавања проблема).
Пример 2.2.9. Израчунајмо временску сложеност наредне рекурзивне функције која израчунава факторијел свог аргумента:
unsigned faktorijel(unsigned n)
{
if (n == 0)
return 1;
else
return n * faktorijel(n-1);
}Нека \(T(n)\) означава број инструкција које захтева позив функције faktorijel за улазну вредност \(n\). За \(n=0\), важи \(T(n)=a\), где је \(a\) нека константа. За \(n>0\), важи \(T(n)=b+T(n-1)\), где је \(b\) нека константа (у том случају извршава се једно поређење, једно одузимање, број инструкција које захтева функција faktorijel за аргумент \(n-1\), једно множење и једна наредба return). Дакле, \(T(n) =b+T(n-1)=b+b+T(n-2)=\ldots=\underbrace{b+b+\ldots+b}_{n}+T(0)=bn + a\) Дакле, наведена функција има линеарну временску сложеност. Скренимо пажњу и на то да вредност факторијела јако брзо расте и да зато веома брзо долази до прекорачења.
Размотримо и просторну сложеност \(S(n)\) функције faktorijel. Једна инстанца функције faktorijel заузима (на програмском стеку) константан простор \(c\). Највише простора је заузето када се извршава рекурзивни позив, те за просторну сложеност важи:
\[S(0) = c\]
\[S(n) = S(n-1) + c\]
одакле се добија да \(S(n)\) припада класи \(O(n)\).
За израчунавање сложености компликованијих рекурзивних функција потребан је математички апарат за решавање рекурентних једначина, у поглављу @sec:rekurentne.
Кључни савет за побољшање сложености је то да рачунар ради само оно што је неопходно да би се добио коначан резултат. Када се та идеја мало детаљније разради, добијамо следећи низ веома једноставних савета који нас често доводе до алгоритама мање сложености:
Ова листа савета, наравно, није исцрпна, али изненађујуће велики број значајних ефикасних алгоритама се суштински заснива на примени баш ових савета.
Уколико перформансе програма нису задовољавајуће, пре било чега другог треба размотрити замену кључних алгоритама – алгоритама који доминантно утичу на сложеност. Постоји низ важних и елементарних и напредних техника које могу помоћи да се снизи сложеност алгоритама и њима ћемо се бавити у наредним поглављима.
Уколико замена алгоритама ефикаснијим не успева тј. уколико се сматра да је асимптотско понашање најбоље могуће, преостаје да се покуша поправљање ефикасности снижавањем константних фактора у функцији која описује сложеност (тиме се не мења асимптотско понашање, али се понекад може донекле смањити укупно утрошено време – на пример, програм се може модификовати тако да извршава \(6n+3\) инструкција уместо \(7n+2\)). Убрзавање програма често захтева специфична решења, али постоје и неке идеје које су применљиве у великом броју случајева.
Модерни компилатори омогућавају додатно подешавање за генерисање ефикаснијег кода. Иако значајно побољшавају перформансе (често константно, али некада и асимптотски), напредне оптимизације носе одређене изазове:
Компилатори обично имају могућност да се експлицитно изабере нека техника оптимизације или ниво оптимизовања (што укључује или не укључује више појединачних техника). На пример, за компилатор gcc ниво оптимизације се бира коришћењем опције -О иза које може бити наведена ознака степена оптимизације:
| Опција | Опис оптимизације |
|---|---|
-O0 |
Подразумевани режим; користи само базичне технике без значајног утицаја на код. |
-O1 |
Балансира величину и брзину; избегава технике које драстично продужавају компилацију. |
-O2 |
Фокус на брзини извршавања; не дозвољава повећање меморијског отиска програма. |
-O3 |
Најагресивнија брзина; дозвољава већи меморијски простор зарад бољих перформанси. |
-Os |
Оптимизација искључиво за смањење величине извршиве датотеке. |
Модерни компилатори су, дакле, у стању да самостално примене измене кода сличне онима које ћемо описати у наставку. Зато треба имати на уму пре свега општи дух наведених примера и начин размишљања који их прати. Поред тога, није добро увек се ослањати на то да ће компилатор све оптимизације извршити аутоматски. Задатак програмера је да провери да ли се то догађа и ако се не догађа, да програм самостално оптимизује, ако је то могуће. Такође, треба имати у виду да ће се програм у неким ситуацијама преводити на другој платформи, помоћу другачијег преводиоца, за који није сигурно какве ће оптимизације вршити. Зато, општи савет може бити да у деловима програма за које програмер очекује да могу представљати уско грло, програмер од почетних фаза пише програм тако да избегне неефикасности, уколико тај начин писања програма не доводи до компликованог и неразумљивог кода. Након иницијалног развоја коректног програма, требало би пажљиво измерити време извршавања програма и његових појединих делова (профилисање), утврдити који критични делови кода нису аутоматски оптимизовани довољно квалитетно и затим покушати њихову оптимизацију самостално.
Програмери често погрешно процењују који делови програма троше највише ресурса. Непроверене оптимизације могу непотребно искомпликовати кôд и отежати одржавање, а да притом не донесу реално побољшање. Зато је кључно:
Увек се треба фокусирати на делове програма који заиста троше највише времена. Ако је утицај неког дела на укупне перформансе занемарљив, боље је да он остане једноставан и лако разумљив.
Чувене су речи Доналда Кнута: ,,Програмери троше енормне количине времена размишљајући или бринући о брзини некритичних делова својих програма и то заправо ствара јак негативан утицај у фазама дебаговања и одржавања. Треба да заборавимо на мале ефикасности, рецимо \(97\%\) времена док програмирамо: прерана оптимизација је корен свих зала. Ипак, не треба да пропустимо могућности у преосталих критичних \(3\%\).``
Приликом оптимизације програма, кључно је разумети колика су реална очекивања од убрзања појединачних делова кода. Амдалов закон нам помаже да квантификујемо максимално могуће убрзање целог система на основу побољшања само једног његовог дела.
Претпоставимо да програм има сегмент који можемо технички унапредити. Дефинишимо следеће параметре:
Ако је укупно време извршавања пре оптимизације \(T\), оно се може представити као збир времена које троши део који се не мења и део који се оптимизује:
\[T = (1 - p)T + pT\]
Након примене оптимизације, време извршавања дела \(p\) се смањује за фактор \(s\), па ново време \(T'\) износи:
\[T' = (1 - p)T + \frac{pT}{s}\]
Укупно убрзање програма (\(S\)) дефинише се као однос старог и новог времена извршавања:
\[S = \frac{T}{T'} = \frac{T}{(1 - p)T + \frac{pT}{s}}\]
Скраћивањем вредности \(T\), добијамо коначну формулу Амдаловог закона:
\[S = \frac{1}{(1 - p) + \frac{p}{s}}\]
Да бисмо боље разумели лимите оптимизације, погледајмо два сценарија где одређену функцију убрзавамо тачно 10 пута (\(s = 10\)).
Пример 2.3.1. Претпоставимо да одређена функција заузима само 10% укупног времена извршавања програма (\(p = 0,1\)). Ако ту функцију убрзамо 10 пута, укупно убрзање ће бити:
\[S = \frac{1}{(1 - 0,1) + \frac{0,1}{10}} = \frac{1}{0,9 + 0,01} \approx 1,1\]
Закључак: Иако смо функцију убрзали драстично (10 пута), цео програм је постао бржи само за око 10%.
Пример 2.3.2. Претпоставимо да иста та функција заузима чак 90% времена извршавања (\(p = 0,9\)). Уз исто убрзање од 10 пута, резултат је:
\[S = \frac{1}{(1 - 0,9) + \frac{0,9}{10}} = \frac{1}{0,1 + 0,09} \approx 5,3\]
Закључак: У овом случају, убрзање читавог програма износи око 5,3 пута. Приметите да чак и када убрзамо 10 пута део који доминира извршавањем, укупно убрзање је далеко мање од 10 пута.
Из ових примера можемо извући неке кључне закључке.
Пример 2.3.3. Илуструјмо, на крају, оптимизацију једним Лојдовим7 проблемом: “Риболовац је сакупио 1кг црва. Сакупљени црви имали су \(1\%\) суве материје и \(99\%\) воде. Сутра, након сушења, црви су имали \(95\%\) воде у себи. Колика је тада била укупна маса црва?” На почетку, сува материја чинила је 1% од 1кг, тј. 10гр. Сутрадан, воде је било 19 пута више од суве материје, тј. 190гр, па је укупна маса црва била 200 грама.
Ако би програм чиниле функције \(f\) и \(g\) и ако би \(f\) покривала \(99\%\) а функција \(g\) 1% времена извршавања, главни кандидат за оптимизовање била би, наравно, функција \(f\). Уколико би њен удео у коначном времену пао са \(99\%\) на \(95\%\), онда би укупно време извршавања програма било сведено на само \(20\%\) почетног.
Идентично скупо израчунавање не би требало понављати. Уместо директног позивања захтевних функција више пута, боље је сачувати њихове вредности у помоћним променљивама.
Пример 2.3.4. Увођењем помоћних променљивих у наредном примеру се смањује број позива тригонометријских функција (које се извршавају релативно споро).
// Manje efikasno: cos i sin se racunaju po dva puta
x = x0*cos(0.01) - y0*sin(0.01);
y = x0*sin(0.01) + y0*cos(0.01);
// Efikasnije:
cs = cos(0.01); sn = sin(0.01);
x = x0*cs - y0*sn;
y = x0*sn + y0*cs;Модерни компилатори (нпр. gcc уз -O1) често сами врше ову оптимизацију. Међутим, то није увек тривијално јер компилатор мора анализом потврдити да функција нема пропратних ефеката и да увек враћа исту вредност за исти аргумент.
Свако израчунавање чији се резултат не мења током итерација треба изнети испред петље.
Пример 2.3.5. Веома слично претходном примеру у наредном коду је још значајније израчунавање вредности тригонометријских функција издвојити ван петље и сачувати у помоћним променљивама.
for (i=0; i < N; i++) {
x = x0*cos(0.01) - y0*sin(0.01);
y = x0*sin(0.01) + y0*cos(0.01);
...
} Ово је посебно важно када се ради о функцијама чија сложеност зависи од величине података.
Пример 2.3.6. У следећем примеру, позивање strlen(s) зa C-овску ниска караткера унутар услова петље драстично нарушава перформансе:
// Losa praksa: slozenost O(n^2) jer se strlen poziva u
// svakoj iteraciji
for (i = 0; i < strlen(s); i++) { ... }
// Bolja praksa: slozenost O(n)
int len = strlen(s);
for (i = 0; i < len; i++) { ... }
...Пошто strlen има линеарну сложеност \(O(n)\), њеним позивањем унутар петље укупно време извршавања постаје квадратно \(O(n^2)\) (ово је још један пример скривене сложености). Ово је пример оптимизације која побољшава асимптотску сложеност програма.
За итерацију кроз ниску у језику C, најбоље је користити проверу терминирајућег карактера \0, чиме се потпуно избегава позивање функције strlen:
for (i = 0; s[i] != '\0'; i++)
if (s[i] == c)
...Ова техника подразумева замену рачунски захтевних („скупих“) операција математички еквивалентним, али хардверски „јефтинијим“ операцијама које се извршавају у мањем броју циклуса процесора. На пример, уколико је могуће добро је избегавати скупе тригонометријске функције, кореновање и слично.
Пример 2.3.7. Чест пример је поређење растојања између тачака. Уместо директног поређења \(\sqrt{x_1^2 + y_1^2} > \sqrt{x_2^2 + y_2^2}\), далеко је ефикасније поредити квадрате растојања: \(x_1^2 + y_1^2 > x_2^2 + y_2^2\). Тиме се у потпуности елиминише позив функције sqrt, која је интерно сложена и захтева много процесорског времена.
Слично, површину троугла је много боље рачунати помоћу векторског производа и детерминанте, него помоћу Хероновог обрасца (који укључује кореновање).
И операције над целим бројевима се могу ослабити. На пример, множења или дељења степеном двојке помоћу битовског шифтовања (на пример, x * 8 је исто што и x << 3, што је операција коју процесор извршава тренутно). Ипак, пошто компилатори овакве трансформације веома често врше у процесу оптимизације, оваквим трансформацијама треба приступити с резервом, јер могу нарушити читљивост кода без икаквог доприноса на брзину извршавања.
Поред замене скупих функција јефинијим, уместо “већих” типова добро је користити мање, пожељно целобројне. Процесори су најбржи када раде са целобројним вредностима (int). Прелазак са децималних (double) на целобројне типове, где год логика програма то дозвољава, доноси значајна убрзања. Такође, мањи типови података боље користе кеш меморију, што смањује број спорих приступа главној меморији (RAM).
Основна идеја претпроцесирања је пребацивање терета израчунавања из фазе извршавања у фазу компилације или иницијализације. Ако се у програму често користе вредности из коначног и релативно малог скупа, ефикасније је израчунати их унапред.
На пример, ако нам је у неком програму често потребно да користимо вредности корена бројева од 1 до 100, уместо да их стално изнова израчунамо, можемо их сместити у константни низ (табелу) у изворном коду и израчунати приликом иницијализације програма. Ово директно мења сложену функцију обичним приступом меморији, што је знатно брже. Овај приступ је класичан пример компромиса између времена и простора (енгл. time-memory tradeoff). Жртвујемо малу количину меморије (простор за низ) како бисмо драстично уштедели на времену извршавања.
У језику C++, на пример, користи се кључна реч constexpr која приморава компилатор да израчуна вредност неког израза већ током самог превођења програма, тако да извршиви програм већ садржи готов резултат.
Избор програмског језика је једна од најважнијих одлука у фази дизајна софтвера. Тај избор директно утиче на баланс између брзине развоја (време програмера) и брзине извршавања (време процесора).
Данас се већина апликација пише у језицима високог нивоа као што је Python. Идеалан је за прототипове, анализу података, вештачку интелигенцију и скрипте где је битно да се кôд напише брзо и да буде читљив. Међутим, Python је интерпретиран језик, што га чини знатно споријим од компилираних језика. Међутим, он често користи библиотеке (попут NumPy или TensorFlow) које су интерно написане у C-у, чиме се добија “најбоље од оба света”.
Када су ресурси ограничени или је брзина критична, програмери се окрећу језицима C и C++. Користе се за развој оперативних система, видео-игара, система за управаље базама података и веб-сервера. Ови језици омогућавају директно управљање меморијом и блиску интеракцију са хардвером, али захтевају много пажљивије програмирање јер грешке често доводе до рушења целог програма.
Иако се данас тежи ка вишим нивоима апстракције, питање језика у којем се пише критични део кода остаје релевантно за системско програмирање и развој софтвера високих перформанси.
Иако савремени компилатори за C и C++ генеришу изванредан машински кôд који ретко који човек може надмашити, асемблер и даље има своје место. Некада је писање критичних делова на асемблеру било стандард за извлачење максимума из процесора. Данас, захваљујући напредним оптимизацијама компилатора ова пракса се све ређе користи. Ипак, асемблер остаје неопходан у системском програмирању, писању драјвера или када је потребно искористити специфичне векторске инструкције процесора (нпр. SIMD) које компилатор можда не користи оптимално.
Од како се хардверски развој више не ослања на драстично повећање радне фреквенције једног језгра, већ на додавање нових језгара, паралелизација је постала кључна за перформансе. Савремени процесори имају 4, 8, 16 или више језгара. Ако је ваш алгоритам секвенцијалан, он користи само делић снаге рачунара. Паралелизација омогућава да се велики задатак подели на мање делове који се извршавају истовремено. Иако писање програма који се могу извршавати на тај начин захтева специфичне програмерске вештине и познавање специјализованих библиотека, оно је све чешће опција.
За разлику од некадашњих рачунара, на савременим рачунарима меморија обично није критични ресурс. Оптимизације се обично усредсређују на штедњу времена или енергије, а не простора. Ипак, постоје ситуације у којима је потребно штедети меморију, на пример, онда када програм барата огромним количинама података, када је с^ам кôд програма велики и заузима значајан део радне меморије (што је данас веома ретко) или када се програм извршава на неком специфичном уређају који има мало меморије.
Наравно, кључни пут ка оптимизацији је поново оптимизација асимптотске меморијске сложености програма тј. замена алгоритама и структура података. Ипак, у неким случајевима поправљање константног фактора може бити значајно (на пример, разлика само у фактору 2 може чинити разлику да ли ће израчунавање бити успешно или неуспешно). Често уштеда меморије захтева специфична решења, али постоје и неке идеје које су применљиве у великом броју случајева:
Користити најмање могуће типове. За целобројне податке, уместо типа int често је довољан тип short или чак char. За представљање реалних бројева, уколико прецизност није критична, може се, уместо типа double користити тип float. За представљање логичких вредности довољан је један бит а више таквих вредности може да се чува у једном бајту (и да им се приступа користећи битовске операторе).
Не чувати оно што може да се лако израчуна. У претходном делу је, у случају да је критична брзина, а не простор, добро да се вредности које се често користе у програму израчунају унапред и укључе у изворни код програма. Уколико је критична меморија, треба урадити управо супротно и не чувати никакве вредности које се могу израчунати у фази извршавања.
Смањење просторне сложености често се постиже повећавањем временске и обратно, али постоје и многе ситуације у којима је добрим решењем могуће поправити истовремено и временску и просторну сложености.
Микросекунда је милионити део секунде, тј. хиљадити део милисекунде и означава се са \(\mu s\).↩︎
Појмови “велико о”, “велико омега” и “велико тета” могу да се уведу и за функције над реалним бројевима, али за потребе анализе сложености израчунавања довољне су верзије за функције над природним бројевима.↩︎
Где су \(f\) и \(g\) функције које зависе од једног или више параметара програма.↩︎
На пример, ако је први део сложености \(O(n)\) а други сложености \(O(n^2)\), онда је укупна временска сложеност \(O(n + n^2)\), што је опет \(O(n^2)\). Тада кажемо да други део програма доминира у времену извршавања.↩︎
Приметимо да ово важи и ако први део ослобађа простор који је заузео. Наиме, \(O(f+g)\) даје просторну сложеност у најгорем случају која истовремено ограничава одозго и \(O(f)\) и \(O(g)\). У оваквој ситуацији просторна сложеност понаша се другачије од временске: ако постоје два дела програма која се извршавају један за другим, укупно време извршавања (не асимптотско ограничење него конкретно утрошено време) једнако је збиру два времена извршавања, а укупни заузети простор једнак је максимуму два заузета простора: један део програма је користио и ослободио неки простор а други део програма је онда делом користио исти тај простор (на пример, на програмском стеку).↩︎
Треба имати на уму да је величина стек оквира за сваку функцију константа, али она може бити веома велика, на пример – ако је у функцији декларисан низ велике димензије. Додатно, треба имати на уму да стек оквири функција заузимају простор на програмском стеку, а простор за њега је обично далеко мањи од меморије у осталим сегментима.↩︎
Samuel Loyd, 1841-1911↩︎