Lad os forenkle algoritmekompleksiteter!

Det er et stykke tid siden jeg begyndte at tænke på at gå tilbage til det grundlæggende og pusse op på kernen i datalogiske begreber. Og jeg regnede med, før jeg hoppede ind i puljen af ​​tunge emner som datastrukturer, operativsystemer, OOP, databaser og systemdesign (seriøst, listen er uendelig) ?, Jeg burde sandsynligvis tage emnet op, som vi alle ikke vil have touch: Analyse af kompleksitet af algoritmer.

Jep! Konceptet, der overses det meste af tiden, fordi flertallet af os udviklere tænker: "Hmm, det behøver jeg sandsynligvis ikke at vide, mens jeg faktisk koder!".?

Jeg er ikke sikker på, om du nogensinde har følt behovet for at forstå, hvordan algoritmeanalyse rent faktisk fungerer. Men hvis du gjorde det, her er mit forsøg på at forklare det på den mest klare måde. Jeg håber, det hjælper en som mig.?

Hvad er algoritmeanalyse alligevel, og hvorfor har vi brug for det? ?

Før vi dykker ned i algoritmekompleksitetsanalyse, lad os først få en kort idé om, hvad algoritmeanalyse er. Algoritmeanalyse handler om at sammenligne algoritmer baseret på antallet af databehandlingsressourcer, som hver algoritme bruger.

Det, vi ønsker at opnå ved denne praksis, er at være i stand til at træffe en informeret beslutning om, hvilken algoritme der er en vinder med hensyn til effektiv udnyttelse af ressourcer (tid eller hukommelse afhængigt af brugssag). Giver dette mening?

Lad os tage et eksempel. Antag, at vi har et funktionsprodukt (), der multiplicerer alle elementerne i en matrix undtagen elementet ved det aktuelle indeks, og returnerer det nye array. Hvis jeg sender [1,2,3,4,5] som input, skal jeg få [120, 60, 40, 30, 24] som resultat.

Ovenstående funktion bruger to indlejrede til sløjfer til at beregne det ønskede resultat. I første omgang tager det elementet på den aktuelle position. I det andet pass multiplicerer det elementet med hvert element i arrayet - undtagen når elementet i den første loop matcher det aktuelle element i den anden loop. I så fald multiplicerer den simpelthen med 1 for at holde produktet uændret.

Kan du følge med? Store!

Det er en enkel tilgang, der fungerer godt, men kan vi gøre det lidt bedre? Kan vi ændre det på en sådan måde, at vi ikke behøver at gøre to anvendte indlejrede sløjfer? Måske gemme resultatet ved hvert pass og bruge det?

Lad os overveje følgende metode. I denne ændrede version er det anvendte princip, at for hvert element skal du beregne produktet af værdierne til højre, beregne produkterne af værdier til venstre og simpelthen gange disse to værdier. Temmelig sød, er det ikke?

Her, i stedet for at bruge indlejrede sløjfer til at beregne værdier ved hver kørsel, bruger vi to ikke-indlejrede sløjfer, hvilket reducerer den samlede kompleksitet med en faktor O (n) (vi kommer til det senere).

Vi kan sikkert udlede, at sidstnævnte algoritme fungerer bedre end den tidligere. Så langt så godt? Perfekt!

På dette tidspunkt kan vi også se hurtigt på de forskellige typer algoritmeanalyse, der findes derude. Vi behøver ikke at gå i detaljer på minutniveauet, men bare have en grundlæggende forståelse af det tekniske jargon.

Afhængig af hvornår en algoritme analyseres, dvs. inden implementering eller efter implementering, kan algoritmeanalyse opdeles i to faser:

  • Apriori-analyse - Som navnet antyder, i apriori (prior) foretager vi analyse (rum og tid) af en algoritme, før vi kører den på et specifikt system. Så grundlæggende er dette en teoretisk analyse af en algoritme. Effektiviteten af ​​en algoritme måles under den antagelse, at alle andre faktorer, f.eks. Processorhastighed, er konstante og ikke har nogen effekt på implementeringen.
  • Apostiari-analyse - Apostiari-analyse af en algoritme udføres kun efter kørsel på et fysisk system. Den valgte algoritme implementeres ved hjælp af et programmeringssprog, der udføres på en målcomputermaskine. Det afhænger direkte af systemkonfigurationer og ændringer fra system til system.

I branchen udfører vi sjældent Apostiari-analyser, da software generelt er lavet til anonyme brugere, der muligvis kører det på forskellige systemer.

Da tid og rums kompleksitet kan variere fra system til system, er Apriori Analyse den mest praktiske metode til at finde algoritmekompleksiteter. Dette skyldes, at vi kun ser på de asymptotiske variationer (vi kommer senere til det) af algoritmen, hvilket giver kompleksiteten baseret på inputstørrelsen snarere end systemkonfigurationer.

Nu hvor vi har en grundlæggende forståelse af, hvad algoritmeanalyse er, kan vi gå videre til vores hovedemne: algoritmekompleksitet. Vi vil fokusere på Apriori-analyse og huske omfanget af dette indlæg, så lad os komme i gang.

Dyb ned i kompleksitet med asymptotisk analyse

Algoritmekompleksitetsanalyse er et værktøj, der giver os mulighed for at forklare, hvordan en algoritme opfører sig, når input bliver større.

Så hvis du f.eks. Vil køre en algoritme med et datasæt med størrelse n , kan vi definere kompleksitet som en numerisk funktion f (n) - tid versus inputstørrelse n .

Nu må du undre dig, er det ikke muligt for en algoritme at tage forskellige mængder tid på de samme indgange, afhængigt af faktorer som processorhastighed, instruktions sæt, diskhastighed og compilatorens mærke? Hvis ja, så klapp dig selv på ryggen, fordi du har helt ret !?

Det er her, asymptotisk analyse kommer ind i dette billede. Her er konceptet at evaluere en algoritmes ydeevne med hensyn til inputstørrelse (uden at måle den faktiske tid, det tager at køre). Så grundlæggende beregner vi, hvordan tiden (eller rummet), som en algoritme tager, stiger, når vi gør inputstørrelsen uendeligt stor.

Kompleksitetsanalyse udføres på to parametre:

  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/
  • En god serie om algoritme og datastrukturer: //interactivepython.org/runestone/static/pythonds/AlgorithmAnalysis/WhatIsAlgorithmAnalysis.html