Поједноставимо сложеност алгоритма!

Прошло је неко време откако сам почео да размишљам о томе да се вратим основама и обрадим основне концепте рачунарске науке. И схватио сам, пре него што ускочим у скуп тешких тема попут структура података, оперативних система, ООП-а, база података и дизајна система (озбиљно, листа је бескрајна), вероватно бих требало да покупим тему коју сви некако не желимо додир: анализа сложености алгоритма.

Иеп! Концепт који се превиди већину времена, јер већина нас програмера размишља, „Хм, вероватно то нећу морати да знам док заправо кодирам!“.?

Па, нисам сигуран да ли сте икада осећали потребу да разумете како анализа алгоритама заправо функционише. Али ако јесте, ево мог покушаја да то објасним на најлуциднији могући начин. Надам се да ће помоћи некоме попут мене.?

Шта је уопште анализа алгоритма и зашто нам је потребна? ?

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

Оно што желимо да постигнемо овом праксом је могућност доношења утемељене одлуке о томе који алгоритам је победник у погледу ефикасног коришћења ресурса (времена или меморије, у зависности од случаја употребе). Да ли то смисла?

Узмимо пример. Претпоставимо да имамо функцијски производ () који множи све елементе низа, осим елемента тренутног индекса, и враћа нови низ. Ако предајем [1,2,3,4,5] као улаз, требало би да добијем [120, 60, 40, 30, 24] као резултат.

Горња функција користи два угнежђена циклуса за израчунавање жељеног резултата. У првом пролазу узима елемент на тренутној позицији. У другом пролазу множи тај елемент са сваким елементом низа - осим када се елемент прве петље подудара са тренутним елементом друге петље. У том случају га једноставно помножи са 1 да би производ остао непромењен.

Можете ли да пратите? Сјајно!

То је једноставан приступ који добро функционише, али можемо ли га побољшати? Можемо ли га модификовати на такав начин да не морамо два пута користити угнежђене петље? Можда чување резултата при сваком додавању и коришћење тога?

Размотримо следећи метод. У овој модификованој верзији примењен је принцип да за сваки елемент израчунамо производ вредности са десне стране, израчунамо производе вредности са леве стране и једноставно помножимо те две вредности. Прилично слатко, зар не?

Овде, уместо да користимо угнежђене петље за израчунавање вредности при сваком извођењу, користимо две неснеђене петље, што смањује укупну сложеност за фактор О (н) (до тога ћемо доћи касније).

Можемо сигурно закључити да се други алгоритам изводи боље од претходног. Засада је добро? Савршен!

У овом тренутку, такође можемо на брзину погледати различите врсте анализа алгоритама које постоје тамо. Не треба да улазимо у детаље на нивоу минута, већ само да основно разумемо технички жаргон.

У зависности од тога када се алгоритам анализира, односно пре или после имплементације, анализа алгоритма може се поделити у две фазе:

  • Априори анализа - Као што и само име говори, у априори (приор) радимо анализу (простор и време) алгоритма пре него што га покренемо на одређеном систему. Тако да је у основи ово теоријска анализа алгоритма. Ефикасност алгоритма мери се под претпоставком да су сви остали фактори, на пример, брзина процесора, константни и немају утицаја на примену.
  • Апостиари анализа - Апостиари анализа алгоритма врши се тек након покретања на физичком систему. Одабрани алгоритам се имплементира помоћу програмског језика који се извршава на циљаној рачунарској машини. То директно зависи од конфигурације система и промена од система до система.

У индустрији ретко вршимо анализу Апостиарија, јер је софтвер углавном направљен за анонимне кориснике који га могу покретати на различитим системима.

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

Сад кад смо основно разумели шта је анализа алгоритма, можемо прећи на нашу главну тему: сложеност алгоритма. Усредсредићемо се на Априори анализу , имајући у виду обим овог поста, па кренимо.

Дубоко зароните у сложеност асимптотском анализом

Анализа сложености алгоритма је алат који нам омогућава да објаснимо како се алгоритам понаша како улаз постаје све већи.

Дакле, ако желите да покренете алгоритам са скупом података величине н , на пример, можемо дефинисати сложеност као нумеричку функцију ф (н) - време у односу на улазну величину н .

Сада се сигурно питате, зар није могуће да алгоритам узима различиту количину времена на истим улазима, у зависности од фактора као што су брзина процесора, скуп инструкција, брзина диска и марка компајлера? Ако јесте, онда се тапшајте по леђима, јер сте потпуно у праву !?

Овде асимптотска анализа долази у ову слику. Овде је концепт процена перформанси алгоритма у смислу величине улаза (без мерења стварног времена потребног за покретање). Дакле, у основи израчунавамо како се време (или простор) које алгоритам узима повећава када улазну величину чинимо бескрајно великом.

Анализа сложености врши се на два параметра:

  1. Време : Временска сложеност показује колико дуго алгоритам треба да се заврши с обзиром на величину уноса. Ресурс који нас брине у овом случају је ЦПУ (и време зидног сата).
  2. Простор : Сложеност простора је слична, али је показатељ колико је меморије „потребно“ за извршавање алгоритма с обзиром на улазну величину. Овде имамо посла са системском РАМ-ом као ресурсом.

Да ли смо још заједно? Добро! Сада постоје различити записи које користимо за анализу сложености путем асимптотске анализе. Проћи ћемо кроз све њих једног по једног и разумети основе иза којих стоји.

Велики ох (Велики О)

Прва и најпопуларнија нотација која се користи за анализу сложености је БигО нотација. Разлог томе је што даје анализу најгорег случаја алгоритма. Штреберски универзум је углавном забринут због тога колико се алгоритам може лоше понашати и како се може учинити да боље функционише. БигО нам пружа управо то.

Уђимо у математичку страну тога да бисмо разумели ствари у њиховој основи.

Размотримо алгоритам који се може описати функцијом ф (н). Дакле, да бисмо дефинисали БигО ф (н) , морамо пронаћи функцију, рецимо, г (н) , која је ограничава. Значи, после одређене вредности, н0, вредност г (н) би увек премашила ф (н) .

Можемо то написати као,

ф (н) ≤ Ц г (н)

где је н≥н0; Ц> 0; н0≥1

If above conditions are fulfilled, we can say that g(n) is the BigO of f(n), or

f(n) = O (g(n))

Can we apply the same to analyze an algorithm? This basically means that in worst case scenario of running an algorithm, the value should not pass beyond a certain point, which is g(n) in this case. Hence, g(n) is the BigO of f(n).

Let’s go through some commonly used bigO notations and their complexity and understand them a little better.

  • O(1): Describes an algorithm that will always execute in the same time (or space) regardless of the size of the input data set.
function firstItem(arr){ return arr[0];}

The above function firstItem(), will always take the same time to execute, as it returns the first item from an array, irrespective of its size. The running time of this function is independent of input size, and so it has a constant complexity of O(1).

Relating it to the above explanation, even in the worst case scenario of this algorithm (assuming input to be extremely large), the running time would remain constant and not go beyond a certain value. So, its BigO complexity is constant, that is O(1).

  • O(N): Describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set. Take a look at the example below. We have a function called matchValue() which returns true whenever a matching case is found in the array. Here, since we have to iterate over the whole of the array, the running time is directly proportional to the size of the array.
function matchValue(arr, k){ for(var i = 0; i < arr.length; i++){ if(arr[i]==k){ return true; } else{ return false; } } }

This also demonstrates how Big O favors the worst-case performance scenario. A matching case could be found during any iteration of the for loop and the function would return early. But Big O notation will always assume the upper limit (worst-case) where the algorithm will perform the maximum number of iterations.

  • O(N²): This represents an algorithm whose performance is directly proportional to the square of the size of the input data set. This is common with algorithms that involve nested iterations over the data set. Deeper nested iterations will result in O(N³), O(N⁴), etc.
function containsDuplicates(arr){ for (var outer = 0; outer < arr.length; outer++){ for (var inner = 0; inner < arr.length; inner++){ if (outer == inner) continue; if (arr[outer] == arr[inner]) return true; } } return false;}
  • O(2^N): Denotes an algorithm whose growth doubles with each addition to the input data set. The growth curve of an O(2^N) function is exponential — starting off very shallow, then rising meteorically. An example of an O(2^N) function is the recursive calculation of Fibonacci numbers:
function recursiveFibonacci(number){ if (number <= 1) return number; return recursiveFibonacci(number - 2) + recursiveFibonacci(number - 1);}

Are you getting the hang of this? Perfect. If not, feel free to fire up your queries in the comments below. :)

Moving on, now that we have a better understanding of the BigO notation, let us get to the next type of asymptotic analysis which is, the Big Omega(Ω).

The Big Omega (Ω)?

The Big Omega(Ω) provides us with the best case scenario of running an algorithm. Meaning, it would give us the minimum amount of resources (time or space) an algorithm would take to run.

Let’s dive into the mathematics of it to analyze it graphically.

We have an algorithm which can be described by a function f(n). So, to define the BigΩ of f(n), we need to find a function, let’s say, g(n), which is tightest to the lower bound of f(n). Meaning, after a certain value, n0, the value of f(n) would always exceed g(n).

We can write it as,

f(n)≥ C g(n)

where n≥n0; C> 0; n0≥1

If above conditions are fulfilled, we can say that g(n) is the BigΩ of f(n), or

f(n) = Ω (g(n))

Can we infer that Ω(…) is complementary to O(…)? Moving on to the last section of this post…

The Big Theta (θ)?

The Big Theta(θ) is a sort of a combination of both BigO and BigΩ. It gives us the average case scenario of running an algorithm. Meaning, it would give us the mean of the best and worst case. Let’s analyse it mathematically.

Considering an algorithm which can be described by a function f(n). The Bigθ of f(n) would be a function, let’s say, g(n), which bounds it the tightest by both lower and upper bound, such that,

C₁g(n) ≤ f(n)≤ C₂ g(n)

whereC₁, C₂ >0, n≥ n0,

n0 ≥ 1

Meaning, after a certain value, n0, the value of C₁g(n) would always be less than f(n), and value of C₂ g(n) would always exceed f(n).

Now that we have a better understanding of the different types of asymptotic complexities, let’s have an example to get a clearer idea of how all this works practically.

Consider an array, of size, say, n, and we want to do a linear search to find an element x in it. Suppose the array looks something like this in the memory.

Going by the concept of linear search, if x=9, then that would be the best case scenario for the following case (as we don’t have to iterate over the whole array). And from what we have just learned, the complexity for this can be written as Ω(1). Makes sense?

Similarly, if x were equal to 14, that would be the worst case scenario, and the complexity would have been O(n).

What would be the average case complexity for this?

θ(n/2) => 1/2 θ(n) => θ(n) (As we ignore constants while calculating asymptotic complexities).

So, there you go folks. A fundamental insight into algorithmic complexities. Did it go well with you? Leave your advice, questions, suggestions in the comments below. Thanks for reading!❤️

References:-

  • A nice write-up by Dionysis “dionyziz” Zindros: //discrete.gr/complexity/
  • Добра серија о алгоритмима и структурама података: //интерацтивепитхон.орг/рунестоне/статиц/питхондс/АлгоритхмАналисис/ВхатИсАлгоритхмАналисис.хтмл