Yksinkertaistetaan algoritmien monimutkaisuutta!

Se on ollut jonkin aikaa siitä, kun aloin ajatella palata perusasioihin ja harjata tietotekniikan ydinkäsitteitä. Ja ajattelin, ennen kuin hyppäsin raskaaseen aiheeseen, kuten tietorakenteet, käyttöjärjestelmät, OOP, tietokannat ja järjestelmäsuunnittelu (vakavasti, luettelo on loputon)? touch: algoritmin monimutkaisuusanalyysi.

Jee! Käsite, joka jätetään huomiotta suurimman osan ajasta, koska suurin osa meistä kehittäjistä ajattelee: "Hmm, minun ei todennäköisesti tarvitse tietää sitä, kun koodaan!"

No, en ole varma, oletko koskaan tuntenut tarvetta ymmärtää, miten algoritmianalyysi todella toimii. Mutta jos teit, tässä yritän selittää sen mahdollisimman selkeällä tavalla. Toivon, että se auttaa minua kaltaista.?

Mikä on algoritmianalyysi joka tapauksessa, ja miksi sitä tarvitaan? ?

Ennen kuin sukeltaa algoritmikompleksianalyysiin, saamme ensin lyhyen käsityksen siitä, mikä algoritmianalyysi on. Algoritmianalyysi käsittelee algoritmien vertailua kunkin algoritmin käyttämän laskentaresurssien määrän perusteella.

Tämän käytännön avulla haluamme tehdä tietoisen päätöksen siitä, mikä algoritmi on voittaja resurssien tehokkaan käytön kannalta (aika tai muisti käyttötapauksesta riippuen). Onko tämä ymmärrettävää?

Otetaan esimerkki. Oletetaan, että meillä on funktiotuote (), joka kertoo kaikki matriisin elementit paitsi nykyisen indeksin elementin ja palauttaa uuden matriisin. Jos ohitan syötteen [1,2,3,4,5], minun pitäisi saada tulokseksi [120, 60, 40, 30, 24].

Yllä olevaa toimintoa käytetään kahta sisäkkäisiä varten silmukoita laskea halutun tuloksen. Ensimmäisellä kierroksella se vie elementin nykyiseen asentoonsa. Toisella kierroksella se kertoo kyseisen elementin matriisin jokaisen elementin kanssa - paitsi kun ensimmäisen silmukan elementti vastaa toisen silmukan nykyistä elementtiä. Siinä tapauksessa se yksinkertaisesti kertoo sen yhdellä, jotta tuote ei muutu.

Pystytkö seuraamaan? Loistava!

Se on yksinkertainen lähestymistapa, joka toimii hyvin, mutta voimmeko tehdä siitä hieman paremman? Voimmeko muokata sitä niin, että meidän ei tarvitse käyttää kahta sisäkkäisten silmukoiden käyttöä? Ehkä tallennat tuloksen jokaisella kierroksella ja hyödynnät sitä?

Tarkastellaan seuraavaa menetelmää. Tässä muokatussa versiossa noudatetaan periaatetta, jonka mukaan jokaiselle elementille lasketaan oikealla olevien arvojen tulo, lasketaan vasemmalla olevien arvojen tulot ja kerrotaan yksinkertaisesti nämä kaksi arvoa. Melko makea, eikö olekin?

Tällöin käytämme kahta sisäkkäistä silmukkaa sen sijaan, että käytämme sisäkkäisiä silmukoita jokaisen ajon arvojen laskemiseksi, mikä vähentää kokonaiskompleksisuutta O (n) -kertoimella (tulemme siihen myöhemmin).

Voimme turvallisesti päätellä, että jälkimmäinen algoritmi toimii paremmin kuin ensimmäinen. Toistaiseksi, niin hyvä? Täydellinen!

Tässä vaiheessa voimme myös tarkastella nopeasti eri tyyppisiä algoritmianalyyseja. Meidän ei tarvitse mennä minuutin tason yksityiskohtiin, mutta meidän on vain ymmärrettävä perusteellisesti tekninen ammattikieltä.

Riippuen siitä, milloin algoritmi analysoidaan, eli ennen käyttöönottoa tai toteutuksen jälkeen, algoritmianalyysi voidaan jakaa kahteen vaiheeseen:

  • Apriori-analyysi - Kuten nimestä voi päätellä, analysoimme apriorissa (ennen) algoritmin (tila ja aika) ennen sen suorittamista tietyssä järjestelmässä. Joten pohjimmiltaan tämä on algoritmin teoreettinen analyysi. Algoritmin tehokkuus mitataan olettaen, että kaikki muut tekijät, esimerkiksi prosessorin nopeus, ovat vakioita eikä niillä ole vaikutusta toteutukseen.
  • Apostiari-analyysi - Algoritmin Apostiari-analyysi suoritetaan vasta sen suorittamisen jälkeen fyysisessä järjestelmässä. Valittu algoritmi toteutetaan käyttäen ohjelmointikieltä, joka suoritetaan kohdetietokoneessa. Se riippuu suoraan järjestelmän kokoonpanoista ja muutoksista järjestelmistä toiseen.

Alalla teemme harvoin Apostiari-analyysiä, koska ohjelmisto on yleensä tehty nimettömille käyttäjille, jotka saattavat käyttää sitä eri järjestelmissä.

Koska ajan ja tilan monimutkaisuus voi vaihdella järjestelmittäin, Apriori-analyysi on käytännöllisin menetelmä algoritmikompleksien löytämiseksi. Tämä johtuu siitä, että tarkastelemme vain algoritmin asymptoottisia muunnelmia (tulemme siihen myöhemmin), mikä antaa monimutkaisuuden tulokoon eikä järjestelmän kokoonpanojen perusteella.

Nyt kun meillä on perustiedot siitä, mikä algoritmianalyysi on, voimme siirtyä eteenpäin pääaiheemme: algoritmien monimutkaisuus. Keskitymme Apriori-analyysiin pitäen mielessä tämän viestin laajuuden, joten aloitetaan.

Sukella syvälle monimutkaisuuteen asymptoottisen analyysin avulla

Algoritmikompleksianalyysi on työkalu, jonka avulla voimme selittää, miten algoritmi käyttäytyy syötteen kasvaessa.

Joten, jos haluat suorittaa algoritmin esimerkiksi tietojoukolla, jonka koko on n , voimme määritellä monimutkaisuuden numeerisena funktiona f (n) - aika verrattuna syötekokoon n .

Nyt sinun on mietittävä, eikö algoritmilla ole mahdollista viedä eri aikoja samoille tuloille riippuen tekijöistä, kuten prosessorin nopeudesta, käskyjoukosta, levyn nopeudesta ja kääntäjän tuotemerkistä? Jos kyllä, taputa itseäsi selälle, koska olet täysin oikeassa !?

Tässä tulee asymptoottinen analyysi tähän kuvaan. Tässä käsitteenä on arvioida algoritmin suorituskyky syötteen koon suhteen (mittaamatta tosiasiallista aikaa, joka kuluu suoritukseen). Joten pohjimmiltaan laskemme kuinka algoritmin käyttämä aika (tai tila) kasvaa kun teemme syötekoon äärettömän suureksi.

Monimutkaisuusanalyysi suoritetaan kahdella parametrilla:

  1. Aika : Ajan monimutkaisuus antaa osoituksen siitä, kuinka kauan algoritmin loppuun saattaminen kestää syötteen kokoon nähden. Resurssi, josta olemme huolissamme tässä tapauksessa, on prosessori (ja seinäkello).
  2. Avaruus : Avaruuden monimutkaisuus on samanlainen, mutta se on osoitus siitä, kuinka paljon muistia "tarvitaan" algoritmin suorittamiseen suhteessa syötteen kokoon. Tässä käsitellään järjestelmän RAM-muistia resurssina.

Oletko edelleen kanssani? Hyvä! Nyt on olemassa erilaisia ​​merkintöjä, joita käytämme analysoimaan monimutkaisuutta asymptoottisen analyysin avulla. Käymme kaikki läpi yksi kerrallaan ja ymmärrämme kunkin taustalla olevat perusteet.

Iso oh (iso O)

Ensimmäinen ja suosituin monimutkaisuusanalyysissä käytetty merkintätapa on BigO-notaatio. Syynä tähän on se, että se antaa algoritmin pahimmassa tapauksessa analyysin. Nörttiuniversumi on enimmäkseen huolissaan siitä, kuinka huonosti algoritmi voi käyttäytyä ja kuinka se voidaan saada toimimaan paremmin. BigO tarjoaa meille juuri sen.

Mennään sen matemaattiselle puolelle ymmärtämään asioita ytimessä.

Tarkastellaan algoritmia, joka voidaan kuvata funktiolla f (n). Joten f (n): n BigO: n määrittelemiseksi meidän on löydettävä funktio, sanotaan, g (n) , joka rajoittaa sen. Tarkoituksena on, että tietyn arvon n0 jälkeen g: n (n) arvo ylittäisi aina f (n): n .

Voimme kirjoittaa sen,

f (n) ≤ C g (n)

missä 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/
  • Hyvä sarja algoritmeista ja tietorakenteista: //interactivepython.org/runestone/static/pythonds/AlgorithmAnalysis/WhatIsAlgorithmAnalysis.html