Lihtsustame algoritmide keerukust!

Juba mõnda aega hakkasin mõtlema põhitõdede juurde naasmise ja arvutiteaduse põhikontseptsioonide täiendamise poole. Ja ma mõtlesin, et enne raskekaaluliste teemade, nagu andmestruktuurid, operatsioonisüsteemid, OOP, andmebaasid ja süsteemikujundus (tõsiselt, loend on lõputu), hüppamist? Peaksin ilmselt valima teema, mida me kõik ei taha touch: algoritmi keerukuse analüüs.

Jah! Mõiste, mis jääb enamasti tähelepanuta, sest enamik meist arendajatest mõtlevad: "Hmm, ma ei pea seda tegelikult teadma, kui ma tegelikult kodeerin!".?

Noh, ma pole kindel, kas olete kunagi tundnud vajadust mõista, kuidas algoritmianalüüs tegelikult töötab. Aga kui sa seda tegid, siis siin on minu püüd selgitada seda võimalikult arusaadaval viisil. Loodan, et see aitab minusugust.?

Mis on algoritmianalüüs üldse ja miks me seda vajame? ?

Enne kui sukelduda algoritmide keerukuse analüüsi, saame kõigepealt lühikese ülevaate sellest, mis on algoritmianalüüs. Algoritmianalüüs tegeleb algoritmide võrdlemisega, lähtudes arvutuslike ressursside arvust, mida iga algoritm kasutab.

Selle praktikaga soovime saavutada teadliku otsuse selle kohta, milline algoritm on ressursside (aeg või mälu, olenevalt kasutusjuhtumist) tõhusa kasutamise osas võitja. Kas see on loogiline?

Võtame näite. Oletame, et meil on funktsiooni toode (), mis korrutab massiivi kõik elemendid, välja arvatud praeguse indeksi element, ja tagastab uue massiivi. Kui ma sisestan sisendina [1,2,3,4,5], peaksin tulemuseks saama [120, 60, 40, 30, 24].

Ülaltoodud funktsiooni kasutab kahte pesastatud jaoks silmuseid arvutada soovitud tulemust. Esimesel läbimisel võtab see elemendi praeguses asendis. Teises läbis korrutab see selle elemendi massiivi iga elemendiga - välja arvatud juhul, kui esimese silmuse element sobib teise silmuse praeguse elemendiga. Sellisel juhul korrutab see selle lihtsalt ühega, et toodet ei muudetaks.

Kas suudate jälgida? Suurepärane!

See on lihtne lähenemine, mis töötab hästi, kuid kas saaksime seda veidi paremaks muuta? Kas me saame seda muuta nii, et me ei pea pesastatud silmuseid kahte korda kasutama? Võib-olla salvestate tulemuse igal läbimisel ja kasutate seda ära?

Vaatleme järgmist meetodit. Selles muudetud versioonis kehtib põhimõte, et iga elemendi jaoks arvutage paremal olevate väärtuste korrutis, arvutage vasakul olevate väärtuste korrutis ja korrutage need kaks väärtust lihtsalt. Päris armas, kas pole?

Selle asemel, et kasutada iga käigu väärtuste arvutamiseks sisestatud silmuseid, kasutame kahte pesastamata silmust, mis vähendab üldist keerukust O (n) teguriga (jõuame selle juurde hiljem).

Võime julgelt järeldada, et viimane algoritm toimib paremini kui esimene. Siiamaani on kõik korras? Täiuslik!

Siinkohal võime ka kiirkorras heita pilgu erinevatele algoritmianalüüsi tüüpidele, mis seal olemas on. Me ei pea laskuma minutitaseme üksikasjadesse, vaid peame lihtsalt mõistma tehnilist žargooni.

Sõltuvalt algoritmi analüüsimise ajast, see tähendab enne rakendamist või pärast rakendamist, saab algoritmianalüüsi jagada kahte etappi:

  • Apriori analüüs - nagu nimigi ütleb, teeme apriori (prior ) osas algoritmi (ruumi ja aja) analüüsi enne selle käivitamist kindlas süsteemis. Nii et põhimõtteliselt on see algoritmi teoreetiline analüüs. Algoritmi efektiivsust mõõdetakse eeldusel, et kõik muud tegurid, näiteks protsessori kiirus, on konstantsed ega mõjuta rakendamist.
  • Apostiari analüüs - algoritmi Apostiari analüüs viiakse läbi alles pärast selle käivitamist füüsilises süsteemis. Valitud algoritm viiakse ellu programmeerimiskeele abil, mis käivitatakse sihtarvuti masinas. See sõltub otseselt süsteemi konfiguratsioonidest ja süsteemsetest muudatustest.

Tööstuses teeme Apostiari analüüsi harva, kuna tarkvara on tavaliselt loodud anonüümsetele kasutajatele, kes võivad seda käitada erinevates süsteemides.

Kuna aja ja ruumi keerukus võib süsteemiti erineda, on Apriori analüüs kõige praktilisem meetod algoritmide keerukuse leidmiseks. Seda seetõttu, et me vaatame ainult algoritmi asümptootilisi variatsioone (jõuame selle juurde hiljem), mis annab keerukuse pigem sisendi suuruse kui süsteemi konfiguratsioonide põhjal.

Nüüd, kui meil on põhiteadmised algoritmianalüüsi kohta, saame liikuda edasi oma põhiteema juurde: algoritmide keerukus. Keskendume Apriori analüüsile , pidades silmas selle postituse ulatust, nii et alustame.

Asümptootilise analüüsiga sukelduge sügavale keerukusse

Algoritmide keerukuse analüüs on tööriist, mis võimaldab meil selgitada, kuidas algoritm käitub sisendi suurenedes.

Niisiis, kui soovite käivitada algoritmi näiteks andmekogumiga, mille suurus on n , võime keerukuse määratleda arvfunktsioonina f (n) - aeg versus sisendi suurus n .

Nüüd peate kindlasti mõtlema, kas algoritmil pole võimalik võtta samade sisendite jaoks palju aega, sõltuvalt sellistest teguritest nagu protsessori kiirus, käskude komplekt, ketta kiirus ja kompilaatori kaubamärk? Kui jah, siis patsuta ennast selili, sest sul on täiesti õigus !?

Siit tuleb sellele pildile asümptootiline analüüs . Siinkohal on kontseptsiooniks algoritmi toimivuse hindamine sisendi suuruse osas (ilma jooksva aja mõõtmiseta). Põhimõtteliselt arvutame välja, kuidas algoritmi aeg (või ruum) suureneb, kui muudame sisendi suuruse lõpmatult suureks.

Keerukuse analüüs viiakse läbi kahel parameetril:

  1. Aeg : aja keerukus näitab, kui kaua algoritmi lõpuleviimine võtab aega sisendi suuruse suhtes. Ressurss, mis meil antud juhul muret teeb, on protsessor (ja seinakellaaeg).
  2. Ruum : Ruumi keerukus on sarnane, kuid see näitab, kui palju mälu on algoritmi käivitamiseks sisendi suuruse suhtes "vaja". Siin käsitleme süsteemi RAM-i kui ressurssi.

Kas sa oled ikka minuga? Hea! Nüüd on erinevaid märke, mida kasutame keerukuse analüüsimiseks asümptootilise analüüsi kaudu. Teeme kõik need ükshaaval läbi ja mõistame igaühe taga olevaid põhitõdesid.

Suur oh (suur O)

Kõige esimene ja kõige keerukam analüüs, mida kasutatakse keerukuse analüüsimiseks, on BigO tähistamine. Selle põhjuseks on see, et see annab algoritmi halvimal juhul analüüsi. Nohikuniversum on enamasti mures selle pärast, kui halvasti algoritm võib käituda ja kuidas seda paremini toimima panna. BigO pakub meile täpselt seda.

Läheme selle matemaatilisse külge, et mõista nende keskmes olevaid asju.

Vaatleme algoritmi, mida saab kirjeldada funktsiooniga f (n). Nii et f (n) BigO määratlemiseks peame leidma funktsiooni, ütleme nii, et g (n) , mis seda piirab. See tähendab, et pärast teatud väärtust n0 ületaks g (n) väärtus alati f (n) .

Me võime selle kirjutada

f (n) ≤ C g (n)

kus n ≥ n0; C> 0; n0 ≥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/
  • Hea seeria algoritmide ja andmestruktuuride kohta: //interactivepython.org/runestone/static/pythonds/AlgorithmAnalysis/WhatIsAlgorithmAnalysis.html