Vienkāršosim algoritmu sarežģītību!

Ir pagājis kāds laiks, kopš es sāku domāt par atgriešanos pie pamatiem un informācijas tehnoloģiju pamatjēdzienu iedziļināšanu. Un es iedomājos, ka, pirms pārietu uz tādu smagsvaru tēmu kopumu kā datu struktūras, operētājsistēmas, OOP, datu bāzes un sistēmu dizains (ja nopietni, saraksts ir bezgalīgs)? Man droši vien vajadzētu izvēlēties tēmu, kuru mēs visi nevēlamies pieskāriens: algoritma sarežģītības analīze.

Jā! Koncepcija, kas lielākoties tiek ignorēta, jo lielākā daļa no mums izstrādātāji domā: “Hmm, man tas, iespējams, nebūs jāzina, kamēr es faktiski kodēju!”.?

Es neesmu pārliecināts, vai jūs kādreiz esat izjutis nepieciešamību saprast, kā algoritmu analīze faktiski darbojas. Bet, ja jūs to izdarījāt, šeit ir mans mēģinājums to izskaidrot pēc iespējas saprotamākā veidā. Es ceru, ka tas palīdzēs tādam kā es.?

Kas vispār ir algoritmu analīze un kāpēc mums tā ir vajadzīga? ?

Pirms ienirt algoritmu sarežģītības analīzē, vispirms gūsim īsu priekšstatu par to, kas ir algoritmu analīze. Algoritmu analīze attiecas uz algoritmu salīdzināšanu, pamatojoties uz katra algoritma izmantoto skaitļošanas resursu skaitu.

Tas, ko mēs vēlamies sasniegt ar šo praksi, ir iespēja pieņemt apzinātu lēmumu par to, kurš algoritms ir ieguvējs, efektīvi izmantojot resursus (laiku vai atmiņu, atkarībā no lietošanas gadījuma). Vai tam ir jēga?

Ņemsim piemēru. Pieņemsim, ka mums ir funkcijas produkts (), kas reizina visus masīva elementus, izņemot pašreizējā indeksa elementu, un atgriež jauno masīvu. Ja es izietu [1,2,3,4,5] kā ievadi, man vajadzētu iegūt [120, 60, 40, 30, 24] kā rezultātu.

Iepriekš funkcija ļauj izmantot divu ligzdotu uz cilpas, lai aprēķinātu vēlamo rezultātu. Pirmajā piegājienā tas aizņem elementu pašreizējā stāvoklī. Otrajā laidienā tas reizina šo elementu ar katru masīva elementu - izņemot gadījumus, kad pirmās cilpas elements sakrīt ar pašreizējo otrās cilpas elementu. Tādā gadījumā tas vienkārši tiek reizināts ar 1, lai produkts netiktu modificēts.

Vai jūs spējat sekot? Lieliski!

Tā ir vienkārša pieeja, kas darbojas labi, bet vai mēs varam to padarīt nedaudz labāku? Vai mēs varam to modificēt tā, ka mums nav jāizmanto ligzdotās cilpas divreiz? Varbūt rezultātu uzglabāšana katrā piespēlē un tā izmantošana?

Apsvērsim šādu metodi. Šajā pārveidotajā versijā tiek piemērots princips, ka katram elementam aprēķiniet labo vērtību vērtību reizinājumu, kreisajā pusē aprēķiniet vērtību reizinājumus un vienkārši reiziniet šīs divas vērtības. Diezgan salds, vai ne?

Tā vietā, lai izmantotu ligzdotas cilpas, lai aprēķinātu vērtības katrā braucienā, mēs izmantojam divas bez ligzdām cilpas, kas samazina kopējo sarežģītību ar koeficientu O (n) (pie tā mēs nonāksim vēlāk).

Mēs varam droši secināt, ka pēdējais algoritms darbojas labāk nekā pirmais. Tik tālu, labi? Lieliski!

Šajā brīdī mēs varam arī ātri apskatīt dažādus algoritmu analīzes veidus, kas pastāv. Mums nav jāiedziļinās minūšu līmeņa detaļās, bet mums vienkārši ir jābūt pamata izpratnei par tehnisko žargonu.

Atkarībā no tā, kad tiek analizēts algoritms, tas ir, pirms ieviešanas vai pēc ieviešanas, algoritmu analīzi var sadalīt divos posmos:

  • Apriori analīze - kā norāda nosaukums, apriori (iepriekš) mēs veicam algoritma (telpas un laika) analīzi pirms tā palaišanas noteiktā sistēmā. Tātad būtībā šī ir algoritma teorētiska analīze. Algoritma efektivitāti mēra, pieņemot, ka visi pārējie faktori, piemēram, procesora ātrums, ir nemainīgi un neietekmē ieviešanu.
  • Apostiari analīze - algoritma Apostiari analīze tiek veikta tikai pēc tā palaišanas fiziskajā sistēmā. Atlasītais algoritms tiek realizēts, izmantojot programmēšanas valodu, kas tiek izpildīta mērķa datorā. Tas tieši ir atkarīgs no sistēmas konfigurācijām un izmaiņām dažādās sistēmās.

Šajā nozarē mēs reti veicam Apostiari analīzi, jo programmatūra parasti tiek veidota anonīmiem lietotājiem, kuri to var palaist dažādās sistēmās.

Tā kā laika un telpas sarežģītība dažādās sistēmās var atšķirties, Apriori analīze ir vispraktiskākā metode algoritmu sarežģītības atrašanai. Tas ir tāpēc, ka mēs aplūkojam tikai algoritma asimptotiskās variācijas (pie tām mēs nonāksim vēlāk), kas piešķir sarežģītību, pamatojoties uz ievades lielumu, nevis uz sistēmas konfigurācijām.

Tagad, kad mums ir pamata izpratne par to, kas ir algoritmu analīze, mēs varam pāriet uz mūsu galveno tēmu: algoritmu sarežģītība. Mēs pievērsīsimies Apriori analīzei , paturot prātā šī ieraksta darbības jomu, tāpēc sāksim.

Dziļi ienirt sarežģītībā ar asimptotisko analīzi

Algoritmu sarežģītības analīze ir rīks, kas ļauj mums izskaidrot, kā algoritms rīkojas, pieaugot ievadam.

Tātad, ja vēlaties palaist algoritmu ar , piemēram, datu kopu n , mēs varam noteikt sarežģītību kā skaitlisko funkciju f (n) - laiks pret ievades lielumu n .

Tagad jums ir jābrīnās, vai algoritmam nav iespējams aizņemt atšķirīgu laiku vienām un tām pašām ieejām atkarībā no tādiem faktoriem kā procesora ātrums, instrukciju kopa, diska ātrums un kompilatora zīmols? Ja jā, tad paglaudiet sevi uz muguras, jo jums ir pilnīga taisnība !?

Šeit šajā attēlā parādās asimptotiskā analīze . Šeit jēdziens ir novērtēt algoritma veiktspēju pēc ievades lieluma (nenovērtējot faktisko laiku, kas vajadzīgs, lai palaistu). Tātad būtībā mēs aprēķinām, kā palielinās algoritma patērētais laiks (vai telpa), kad mēs ievades lielumu padarām bezgalīgi lielu.

Sarežģītības analīzi veic diviem parametriem:

  1. Laiks : Laika sarežģītība norāda, cik ilgi algoritms ir jāpabeidz, ņemot vērā ievades lielumu. Resurss, par kuru mēs šajā gadījumā uztraucamies, ir centrālais procesors (un sienas pulksteņa laiks).
  2. Kosmoss : Kosmosa sarežģītība ir līdzīga, taču tā norāda, cik daudz atmiņas ir “nepieciešams” algoritma izpildei attiecībā pret ievades lielumu. Šeit mēs runājam par sistēmas RAM kā resursu.

Vai jūs joprojām esat ar mani? Labi! Tagad ir dažādi apzīmējumi, kurus mēs izmantojam, analizējot sarežģītību, izmantojot asimptotisko analīzi. Mēs tos visus iziesim pa vienam un sapratīsim katra pamatā esošos pamatus.

Lielais ak (lielais O)

Pirmais un populārākais apzīmējums, ko izmanto sarežģītības analīzē, ir BigO apzīmējums. Iemesls tam ir tāds, ka tā sniedz algoritma sliktāko gadījumu analīzi. Nerd Visumu galvenokārt uztrauc tas, cik slikti algoritms var uzvesties un kā to var panākt, lai tas darbotos labāk. BigO mums nodrošina tieši to.

Iedziļināsimies matemātiskajā pusē, lai saprastu lietas to pamatā.

Apskatīsim algoritmu, kuru var aprakstīt ar funkciju f (n). Tātad, lai definētu f (n) BigO , mums jāatrod funkcija, teiksim, g (n) , kas to ierobežo. Tas nozīmē, ka pēc noteiktas vērtības n0 g (n) vērtība vienmēr pārsniegtu f (n) .

Mēs varam to uzrakstīt kā

f (n) ≤ C g (n)

kur 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/
  • Laba sērija par algoritmiem un datu struktūrām: //interactivepython.org/runestone/static/pythonds/AlgorithmAnalysis/WhatIsAlgorithmAnalysis.html