Supaprastinkime algoritmų sudėtingumą!

Praėjo šiek tiek laiko, kai pradėjau galvoti apie grįžimą prie pagrindų ir atnaujinti pagrindines informatikos koncepcijas. Ir aš supratau, kad prieš pereidamas į sunkiasvorių temų, tokių kaip duomenų struktūros, operacinės sistemos, OOP, duomenų bazės ir sistemos dizainas (rimtai, sąrašas yra begalinis), turėčiau pasirinkti temą, kurios mes visi nenorime prisilietimas: algoritmo sudėtingumo analizė.

Taip! Ši koncepcija dažniausiai nepastebima, nes dauguma kūrėjų galvoja: „Hmm, man tikriausiai nereikės to žinoti, kol iš tikrųjų koduoju!“.

Na, nesu tikras, ar kada nors jautėte poreikį suprasti, kaip iš tikrųjų veikia algoritmų analizė. Bet jei jūs tai padarėte, tai aš bandau tai paaiškinti kuo aiškiau. Tikiuosi, kad tai padės tokiam kaip aš.?

Kas vis dėlto yra algoritmo analizė ir kam ji mums reikalinga? ?

Prieš pasinerdami į algoritmų sudėtingumo analizę, pirmiausia trumpai įsivaizduokime, kas yra algoritmo analizė. Algoritmo analizė apima algoritmų palyginimą, pagrįstą skaičiavimo išteklių skaičiumi, kurį naudoja kiekvienas algoritmas.

Tai, ko mes norime pasiekti taikydami šią praktiką, yra galimybė priimti pagrįstą sprendimą dėl to, kuris algoritmas yra efektyviausias išteklių (laiko ar atminties, atsižvelgiant į naudojimo atvejį) naudojimas. Ar tai turi prasmę?

Paimkime pavyzdį. Tarkime, kad turime funkcijos produktą (), kuris padaugina visus masyvo elementus, išskyrus dabartinio indekso elementą, ir grąžina naują masyvą. Jei perduodu [1,2,3,4,5] kaip įvestį, turėčiau gauti [120, 60, 40, 30, 24].

Pirmiau funkcija leidžia naudoti du įdėtos kilpomis apskaičiuoti norimą rezultatą. Pirmajame leidime jis užima elementą dabartinėje padėtyje. Antruoju leidimu jis padaugina tą elementą su kiekvienu masyvo elementu, išskyrus atvejus, kai pirmosios kilpos elementas sutampa su dabartiniu antrosios kilpos elementu. Tokiu atveju jis paprasčiausiai padauginamas iš 1, kad produktas nebūtų modifikuotas.

Ar sugebate sekti? Puiku!

Tai paprastas būdas, kuris gerai veikia, bet ar galime jį padaryti šiek tiek geresnį? Ar galime jį modifikuoti taip, kad nereikėtų naudoti dviejų įdėtų kilpų? Gal saugoti rezultatą kiekviename leidime ir tuo pasinaudoti?

Apsvarstykime šį metodą. Šioje modifikuotoje versijoje taikomas principas, kad kiekvienam elementui apskaičiuokite dešinėje esančių reikšmių sandaugą, kairėje apskaičiuokite verčių sandaugas ir paprasčiausiai padauginkite šias dvi reikšmes. Gana miela, ar ne?

Čia užuot naudoję įdėtąsias kilpas kiekvieno bėgimo reikšmėms apskaičiuoti, mes naudojame dvi ne įdėtas kilpas, o tai sumažina bendrą sudėtingumą O (n) koeficientu (prie to darysime vėliau).

Galime drąsiai daryti išvadą, kad pastarasis algoritmas veikia geriau nei pirmasis. Kol kas viskas gerai? Puikus!

Šiuo metu mes taip pat galime greitai pažvelgti į skirtingus algoritmų analizės tipus. Mums nereikia gilintis į smulkių detalių detales, bet tiesiog reikia gerai suprasti techninį žargoną.

Priklausomai nuo to, kada analizuojamas algoritmas, ty prieš diegiant ar įgyvendinus, algoritmo analizę galima suskirstyti į du etapus:

  • Apriori analizė - kaip rodo pavadinimas, apriori (prieš), mes atlikome algoritmo analizę (erdvę ir laiką) prieš paleidžiant jį konkrečioje sistemoje. Taigi iš esmės tai yra teorinė algoritmo analizė. Algoritmo efektyvumas matuojamas darant prielaidą, kad visi kiti veiksniai, pavyzdžiui, procesoriaus greitis, yra pastovūs ir neturi jokio poveikio įgyvendinimui.
  • Apostiari analizė - Apostiari algoritmo analizė atliekama tik ją paleidus fizinėje sistemoje. Pasirinktas algoritmas įgyvendinamas naudojant programavimo kalbą, kuri vykdoma tikslinėje kompiuterio mašinoje. Tai tiesiogiai priklauso nuo sistemos konfigūracijų ir pokyčių kiekvienoje sistemoje.

Pramonėje mes retai atliekame „Apostiari“ analizę, nes programinė įranga paprastai yra sukurta anoniminiams vartotojams, kurie gali ją paleisti skirtingose ​​sistemose.

Kadangi laiko ir erdvės sudėtingumas gali skirtis priklausomai nuo sistemos, Apriori analizė yra pats praktiškiausias būdas nustatyti algoritmų sudėtingumą. Taip yra todėl, kad mes žiūrime tik į asimptotinius algoritmo variantus (prie jų darysime vėliau), kurie suteikia sudėtingumą, atsižvelgiant į įvesties dydį, o ne į sistemos konfigūracijas.

Dabar, kai turime pagrindinį supratimą apie tai, kas yra algoritmų analizė, galime pereiti prie savo pagrindinės temos: algoritmų sudėtingumo. Mes sutelksime dėmesį į „ Apriori“ analizę , turėdami omenyje šio įrašo apimtį, todėl pradėkime.

Giliai pasinerkite į sudėtingumą, atlikdami asimptotinę analizę

Algoritmo sudėtingumo analizė yra įrankis, leidžiantis mums paaiškinti, kaip algoritmas elgiasi, kai įvestis auga.

Taigi, jei norite paleisti algoritmą , pvz., Su duomenų rinkiniu, kurio dydis yra n , sudėtingumą galime apibrėžti kaip skaitinę funkciją f (n) - laikas, palyginti su įvesties dydžiu n .

Dabar jūs turite įdomu, argi ne algoritmas gali užtrukti skirtingą laiką toms pačioms įvestims, priklausomai nuo tokių veiksnių kaip procesoriaus greitis, komandų rinkinys, disko greitis ir kompiliatoriaus prekės ženklas? Jei taip, tada paglostyk sau nugarą, nes tu esi visiškai teisus !?

Čia šiame paveikslėlyje pateikiama asimptotinė analizė . Čia siekiama įvertinti algoritmo našumą atsižvelgiant į įvesties dydį (nematuojant tikrojo laiko, kurio reikia jo veikimui). Taigi iš esmės mes apskaičiuojame, kaip algoritmo laikas (arba erdvė) didėja, kai įvesties dydis tampa be galo didelis.

Sudėtingumo analizė atliekama dviem parametrais:

  1. Laikas : Laiko sudėtingumas nurodo, kiek laiko reikia atlikti algoritmui, atsižvelgiant į įvesties dydį. Šaltinis, kuris mums rūpi šiuo atveju, yra procesorius (ir laikas nuo sienos laikrodžio).
  2. Erdvė : Erdvės sudėtingumas yra panašus, tačiau tai rodo, kiek atminties „reikia“ algoritmui vykdyti atsižvelgiant į įvesties dydį. Čia mes kalbame apie sistemos RAM kaip šaltinį.

Ar tu vis dar su manimi? Gerai! Dabar yra įvairių žymėjimų, kuriuos naudojame analizuodami sudėtingumą, atlikdami asimptotinę analizę. Mes pereisime juos visus po vieną ir suprasime kiekvieno pagrindinius dalykus.

Didysis ohas (didelis O)

Pirmasis ir populiariausias žymėjimas, naudojamas sudėtingumo analizei, yra „BigO“ žymėjimas. To priežastis yra ta, kad ji pateikia blogiausio atvejo algoritmo analizę. Vėpla visata dažniausiai yra susirūpinusi, kaip blogai gali elgtis algoritmas ir kaip tai padaryti geriau. „BigO“ mums teikia būtent tai.

Pažvelkime į matematinę jos pusę, kad suprastume dalykus, kurie yra jų esmė.

Panagrinėkime algoritmą, kurį galima apibūdinti funkcija f (n). Taigi, norėdami apibrėžti f (n) BigO , turime rasti funkciją, tarkime, g (n) , kuri ją riboja. Reiškia, po tam tikros vertės n0 g (n) reikšmė visada viršija f (n) .

Mes galime tai parašyti kaip

f (n) ≤ C g (n)

kur n ≥n0; C> 0; n0 ≥1

Jei tenkinamos pirmiau nurodytos sąlygos, galime sakyti, kad g (n) yra f (n) BigO arba

f (n) = O (g (n))

Ar galime tą patį pritaikyti analizuodami algoritmą? Iš esmės tai reiškia, kad blogiausiu atveju, kai paleidžiamas algoritmas, reikšmė neturi būti didesnė už tam tikrą tašką, kuris šiuo atveju yra g (n) . Vadinasi, g (n) yra f (n) BigO .

Peržiūrėkime keletą dažniausiai naudojamų „bigO“ žymėjimų ir jų sudėtingumą ir šiek tiek geriau juos suprasime.

  • O (1): apibūdina algoritmą, kuris visada bus vykdomas tuo pačiu metu (arba erdvėje), neatsižvelgiant į įvesties duomenų rinkinio dydį.
function firstItem(arr){ return arr[0];}

Pirmiau nurodyta funkcija firstItem () visada užtruks tą patį laiką, nes grąžina pirmąjį elementą iš masyvo, neatsižvelgiant į jo dydį. Šios funkcijos veikimo laikas nepriklauso nuo įvesties dydžio, todėl ji turi nuolatinį O (1) sudėtingumą.

Susiejus jį su aukščiau pateiktu paaiškinimu, net ir blogiausiu šio algoritmo atveju (darant prielaidą, kad įvestis yra itin didelė), važiavimo laikas išliktų pastovus ir neviršytų tam tikros vertės. Taigi, jo „BigO“ sudėtingumas yra pastovus, tai yra O (1).

  • O (N): apibūdina algoritmą, kurio našumas augs tiesiškai ir tiesiogiai proporcingas įvesties duomenų rinkinio dydžiui. Pažvelkite į žemiau pateiktą pavyzdį. Mes turime funkciją, vadinamą matchValue ( ), kuri grąžina teisingą, kai masyve randamas atitikimo atvejis. Kadangi turime kartoti visą masyvą, veikimo laikas yra tiesiogiai proporcingas masyvo dydžiui.
function matchValue(arr, k){ for(var i = 0; i < arr.length; i++){ if(arr[i]==k){ return true; } else{ return false; } } }

Tai taip pat parodo, kaip „Big O“ palaiko blogiausio įvykio scenarijų. Atitinkamą atvejį galima rasti bet kokio ciklo iteracijos metu forir funkcija grįš anksti. Bet „Big O“ žymėjimas visada prisiims viršutinę ribą (blogiausiu atveju), kur algoritmas atliks maksimalų pakartojimų skaičių.

  • O (N²): Tai reiškia algoritmą, kurio veikimas yra tiesiogiai proporcingas įvesties duomenų rinkinio dydžio kvadratui. Tai būdinga algoritmams, kurie apima įdėtas duomenų rinkinio iteracijas. Giliau įdėtos iteracijos sukels O (N3), O (N⁴) ir kt.
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): reiškia algoritmą, kurio augimas padvigubėja kiekvieną kartą papildant įvesties duomenų rinkinį. O (2 ^ N) funkcijos augimo kreivė yra eksponentinė - pradedama nuo labai seklios, tada kyla meteoriškai. O (2 ^ N) funkcijos pavyzdys yra rekursyvus „Fibonači“ skaičių skaičiavimas:
function recursiveFibonacci(number){ if (number <= 1) return number; return recursiveFibonacci(number - 2) + recursiveFibonacci(number - 1);}

Ar jūs tai suprantate? Puikus. Jei ne, nedvejodami pateikite savo klausimus žemiau esančiuose komentaruose. :)

Dabar, kai geriau suprantame „BigO“ žymėjimą, pereikime prie kito asimptotinės analizės tipo - „Big Omega“ (Ω).

Didžioji omega (Ω) ?

Big Omega“ (Ω) pateikia geriausią algoritmo paleidimo scenarijų. Reiškia, tai suteiktų mums minimalų išteklių (laiko ar vietos) kiekį, kurio prireiks algoritmui paleisti.

Pasinerkime į jos matematiką, kad grafiškai ją išanalizuotume.

Mes turime algoritmą, kurį galima apibūdinti funkcija f (n). Taigi, norėdami apibrėžti f (n) BigΩ , turime rasti funkciją, tarkime, g (n) , kuri yra griežčiausia apatinei f (n) ribai . Reiškia, po tam tikros vertės n0 f (n) reikšmė visada viršija g (n) .

Mes galime tai parašyti kaip

f (n) ≥ C g (n)

kur n ≥n0; C> 0; n0 ≥1

Jei tenkinamos pirmiau nurodytos sąlygos, galime sakyti, kad g (n) yra f (n) BigΩ , arba

f (n) = Ω (g (n))

Ar galime daryti išvadą, kad Ω (…) papildo O (…)? Pereinama prie paskutinės šio įrašo skilties ...

Didžioji teta (θ) ?

T jis Didelis teta (θ) yra iš abiejų Bigo ir BigΩ kartu rūšiuoti. Tai suteikia mums vidutinį algoritmo paleidimo scenarijų. Reiškia, tai suteiktų geriausio ir blogiausio atvejo vidurkį. Panagrinėkime jį matematiškai.

Atsižvelgiant į algoritmą, kurį galima apibūdinti funkcija f (n). Didelis f (n) būtų funkcija, sakykime, g (n) , kuri ją griežčiausiai riboja tiek apatine, tiek viršutine riba, tokia,

C₁g (n) ≤ f (n) ≤ C₂ g (n)

kurC₁, 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/
  • Gera algoritmų ir duomenų struktūrų serija: //interactivepython.org/runestone/static/pythonds/AlgorithmAnalysis/WhatIsAlgorithmAnalysis.html