Semplifichiamo le complessità degli algoritmi!

È passato un po 'di tempo da quando ho iniziato a pensare di tornare alle basi e rispolverare i concetti fondamentali dell'informatica. E ho pensato, prima di saltare nel pool di argomenti pesanti come strutture dati, sistemi operativi, OOP, database e progettazione di sistemi (seriamente, l'elenco è infinito) ?, probabilmente dovrei riprendere l'argomento che tutti noi non vogliamo tocco: algoritmo Analisi della complessità.

Sì! Il concetto che viene trascurato la maggior parte del tempo, perché la maggior parte di noi sviluppatori pensa, "Hmm, probabilmente non avrò bisogno di saperlo mentre codice!".

Beh, non sono sicuro che tu abbia mai sentito il bisogno di capire come funziona effettivamente l'analisi degli algoritmi. Ma se l'hai fatto, ecco il mio tentativo di spiegarlo nel modo più lucido possibile. Spero che aiuti qualcuno come me.

Che cos'è comunque l'analisi algoritmica e perché ne abbiamo bisogno? ?

Prima di immergerci nell'analisi della complessità dell'algoritmo, diamo prima una breve idea di cosa sia l'analisi dell'algoritmo. L'analisi degli algoritmi si occupa del confronto degli algoritmi in base al numero di risorse di calcolo utilizzate da ciascun algoritmo.

Ciò che vogliamo ottenere con questa pratica è essere in grado di prendere una decisione informata su quale algoritmo è vincente in termini di utilizzo efficiente delle risorse (tempo o memoria, a seconda del caso d'uso). ha senso?

Facciamo un esempio. Supponiamo di avere una funzione product () che moltiplica tutti gli elementi di un array, eccetto l'elemento all'indice corrente, e restituisce il nuovo array. Se sto passando [1,2,3,4,5] come input, dovrei ottenere [120, 60, 40, 30, 24] come risultato.

La funzione precedente fa uso di due cicli for annidati per calcolare il risultato desiderato. Nel primo passaggio, prende l'elemento nella posizione corrente. Nel secondo passaggio, moltiplica quell'elemento con ogni elemento dell'array, tranne quando l'elemento del primo ciclo corrisponde all'elemento corrente del secondo ciclo. In tal caso, lo moltiplica semplicemente per 1 per mantenere il prodotto non modificato.

Riesci a seguire? Grande!

È un approccio semplice che funziona bene, ma possiamo migliorarlo leggermente? Possiamo modificarlo in modo tale da non dover fare due usi di cicli annidati? Forse memorizzare il risultato ad ogni passaggio e utilizzarlo?

Consideriamo il seguente metodo. In questa versione modificata, il principio applicato è che per ogni elemento, calcolare il prodotto dei valori a destra, calcolare i prodotti dei valori a sinistra e semplicemente moltiplicare quei due valori. Abbastanza dolce, non è vero?

Qui, invece di fare uso di cicli annidati per calcolare i valori ad ogni esecuzione, usiamo due cicli non annidati, che riducono la complessità complessiva di un fattore O (n) (ci arriveremo più avanti).

Possiamo inferire con sicurezza che il secondo algoritmo funziona meglio del primo. Fin qui tutto bene? Perfetto!

A questo punto, possiamo anche dare una rapida occhiata ai diversi tipi di analisi degli algoritmi che esistono là fuori. Non abbiamo bisogno di entrare nei dettagli a livello minuto, ma abbiamo solo bisogno di avere una conoscenza di base del gergo tecnico.

A seconda di quando un algoritmo viene analizzato, cioè prima o dopo l'implementazione, l'analisi dell'algoritmo può essere suddivisa in due fasi:

  • Analisi Apriori - Come suggerisce il nome, in apriori (precedente), eseguiamo l'analisi (spazio e tempo) di un algoritmo prima di eseguirlo su un sistema specifico. Quindi, fondamentalmente, questa è un'analisi teorica di un algoritmo. L'efficienza di un algoritmo viene misurata assumendo che tutti gli altri fattori, ad esempio la velocità del processore, siano costanti e non abbiano alcun effetto sull'implementazione.
  • Analisi Apostiari - L'analisi Apostiari di un algoritmo viene eseguita solo dopo averla eseguita su un sistema fisico. L'algoritmo selezionato viene implementato utilizzando un linguaggio di programmazione che viene eseguito su un computer di destinazione. Dipende direttamente dalle configurazioni di sistema e dalle modifiche da sistema a sistema.

Nel settore, eseguiamo raramente analisi Apostiari, poiché il software è generalmente realizzato per utenti anonimi che potrebbero eseguirlo su sistemi diversi.

Poiché la complessità temporale e spaziale può variare da sistema a sistema, l'Analisi Apriori è il metodo più pratico per trovare le complessità degli algoritmi. Questo perché guardiamo solo alle variazioni asintotiche (ci arriveremo più avanti) dell'algoritmo, che fornisce la complessità in base alla dimensione dell'input piuttosto che alle configurazioni del sistema.

Ora che abbiamo una comprensione di base di cosa sia l'analisi algoritmica, possiamo passare al nostro argomento principale: la complessità dell'algoritmo. Ci concentreremo sull'analisi Apriori , tenendo presente lo scopo di questo post, quindi iniziamo.

Immergiti nella complessità con l'analisi asintotica

L'analisi della complessità dell'algoritmo è uno strumento che ci consente di spiegare come si comporta un algoritmo man mano che l'input aumenta.

Quindi, se vuoi eseguire un algoritmo con un set di dati di dimensione n , ad esempio, possiamo definire la complessità come una funzione numerica f (n) - tempo rispetto alla dimensione di input n .

Ora ti starai chiedendo, non è possibile che un algoritmo impieghi diverse quantità di tempo sugli stessi ingressi, a seconda di fattori come la velocità del processore, il set di istruzioni, la velocità del disco e la marca del compilatore? Se sì, allora datti una pacca sulla spalla, perché hai assolutamente ragione !?

È qui che entra in gioco l' analisi asintotica . In questo caso, il concetto è valutare le prestazioni di un algoritmo in termini di dimensione dell'input (senza misurare il tempo effettivo necessario per l'esecuzione). Quindi, fondamentalmente, calcoliamo come il tempo (o lo spazio) preso da un algoritmo aumenta man mano che la dimensione dell'input è infinitamente grande.

L'analisi della complessità viene eseguita su due parametri:

  1. Time: Time complexity gives an indication as to how long an algorithm takes to complete with respect to the input size. The resource which we are concerned about in this case is CPU (and wall-clock time).
  2. Space: Space complexity is similar, but is an indication as to how much memory is “required” to execute the algorithm with respect to the input size. Here, we dealing with system RAM as a resource.

Are you still with me? Good! Now, there are different notations which we use for analyzing complexity through asymptotic analysis. We will go through all of them one by one and understand the fundamentals behind each.

The Big oh (Big O)

The very first and most popular notation used for complexity analysis is BigO notation. The reason for this is that it gives the worst case analysis of an algorithm. The nerd universe is mostly concerned about how badly an algorithm can behave, and how it can be made to perform better. BigO provides us exactly that.

Let’s get into the mathematical side of it to understand things at their core.

Let’s consider an algorithm which can be described by a function f(n). So, to define the BigO of f(n), we need to find a function, let’s say, g(n), which bounds it. Meaning, after a certain value, n0, the value of g(n) would always exceed f(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 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/
  • A good series on algorithm & data structures: //interactivepython.org/runestone/static/pythonds/AlgorithmAnalysis/WhatIsAlgorithmAnalysis.html