de Michael Olorunnisola

Algoritmi în engleză simplă: complexitatea timpului și notația Big-O

Algoritmi in engleza simpla complexitatea timpului si notatia Big O

Fiecare dezvoltator bun are timp în minte. Vor să le ofere utilizatorilor mai mult, astfel încât să poată face toate acele lucruri de care se bucură. Acestea fac acest lucru minimizând complexitatea timpului.

Înainte de a putea înțelege complexitatea timpului în programare, trebuie să înțelegeți unde se aplică cel mai frecvent: în proiectarea algoritmi.

Deci, ce este un algoritm, oricum?

Pur și simplu, un algoritm este o serie de pași conținuți, pe care îi urmați pentru a atinge un anumit scop sau pentru a produce o ieșire. Să luăm, de exemplu, rețeta bunicii tale pentru coacerea unui tort. Stai, asta contează ca un algoritm? Sigur că da!

function BakeCake(flavor, icing){
"
 1. Heat Oven to 350 F
 2. Mix flour, baking powder, salt
 3. Beat butter and sugar until fluffy
 4. Add eggs.
 5. Mix in flour, baking powder, salt
 6. Add milk and " + flavor + "
 7. Mix further
 8. Put in pan
 9. Bake for 30 minutes
10." + if(icing === true) return 'add icing' + "
10. Stuff your face
"
}

BakeCake('vanilla', true) => deliciousness

Algoritmii sunt utili în examinarea complexității timpului, deoarece vin în toate formele și dimensiunile.

În același mod, puteți tăia o plăcintă cu 100 de moduri diferite, puteți rezolva o singură problemă cu mulți algoritmi diferiți. Unele soluții sunt mai eficiente, necesită mai puțin timp și necesită mai puțin spațiu decât altele.

Deci, întrebarea principală este: cum mergem pentru a analiza ce soluții sunt cele mai eficiente?

Matematică pentru salvare! Analiza complexității timpului în programare este doar un mod matematic extrem de simplificat de a analiza cât va dura un algoritm cu un anumit număr de intrări (n) pentru a-și finaliza sarcina. De obicei este definit folosind Notare Big-O.

Ce este notația Big O, întrebi?

Dacă promiți că nu vei renunța și nu vei mai citi, îți voi spune.

Notarea Big-O este o modalitate de a converti etapele generale ale unui algoritm în termeni algebrici, excluzând apoi constantele și coeficienții de ordin inferior care nu au un impact atât de mare asupra complexității generale a problemei.

Probabil că matematicienii se vor descurca puțin la presupunerea mea de „impact general”, dar pentru ca dezvoltatorii să economisească timp, este mai ușor să simplificați lucrurile în acest fel:

Regular       Big-O

2             O(1)   --> It's just a constant number

2n + 10       O(n)   --> n has the largest effect

5n^2          O(n^2) --> n^2 has the largest effect

Pe scurt, tot acest exemplu spune că: ne uităm doar la factorul din expresia noastră care are potențialul cel mai mare impact asupra valorii pe care o va întoarce expresia noastră. (Acest lucru se schimbă pe măsură ce constanta devine extrem de mare și n devine mică, dar să nu ne facem griji pentru asta pentru moment).

Mai jos sunt câteva complexități de timp comune cu definiții simple. Simțiți-vă liber să verificați Wikipedia, totuși, pentru definiții mai aprofundate.

  • O (1) – Timp constant: Având o intrare de dimensiunea n, este nevoie doar de un singur pas pentru ca algoritmul să îndeplinească sarcina.
  • O (jurnal n) – Timp logaritmic: având în vedere o intrare de dimensiunea n, numărul de pași necesari pentru îndeplinirea sarcinii este redus cu un anumit factor cu fiecare pas.
  • O (n) – Timp liniar: având în vedere o intrare de dimensiunea n, numărul de pași necesari este direct legat (1 la 1)
  • O (n²) – Timp quadratic: Având o intrare de dimensiunea n, numărul de pași necesari pentru a realiza o sarcină este pătrat de n.
  • O (C ^ n) – Timp exponențial: Având o intrare de dimensiunea n, numărul de pași necesari pentru a realiza o sarcină este o constantă la puterea n (număr destul de mare).

Cu aceste cunoștințe în mână, să vedem numărul de pași pe care îi implică fiecare dintre aceste complexități de timp:

let n = 16;

O (1) = 1 step "(awesome!)"

O (log n) = 4 steps  "(awesome!)" -- assumed base 2

O (n) = 16 steps "(pretty good!)"

O(n^2) = 256 steps "(uhh..we can work with this?)"

O(2^n) = 65,536 steps "(...)"

După cum puteți vedea, lucrurile pot deveni cu ușurință ordine de mărime mai complexe, în funcție de complexitatea algoritmului dvs. Din fericire, calculatoarele sunt suficient de puternice încât să poată gestiona relativ rapid complexitățile cu adevărat mari.

Deci, cum putem face analiza codului nostru cu notația Big-O?

Iată câteva exemple rapide și simple despre cum puteți aplica aceste cunoștințe algoritmilor pe care i-ați putea întâlni în sălbăticie sau să vă codificați singuri.

Vom folosi structurile de date de mai jos pentru exemplele noastre:

var friends = {
 'Mark' : true,
 'Amy' : true,
 'Carl' : false,
 'Ray' :  true,
'Laura' : false,
}
var sortedAges = [22, 24, 27, 29, 31]

O (1) – Timp constant

Căutările de valoare atunci când știți cheia (obiectele) sau indexul (matrici) fac întotdeauna un pas și, prin urmare, sunt timpul constant.

//If I know the persons name, I only have to take one step to check:

function isFriend(name){ //similar to knowing the index in an Array 
  return friends[name]; 
};

isFriend('Mark') // returns True and only took one step

function add(num1,num2){ // I have two numbers, takes one step to return the value
 return num1 + num2
}

O (jurnal n) – Timpul logaritmic

Dacă știți pe ce parte a matricei trebuie să căutați un articol, economisiți timp tăind cealaltă jumătate.

//You decrease the amount of work you have to do with each step

function thisOld(num, array){
  var midPoint = Math.floor( array.length /2 );
  if( array[midPoint] === num) return true;
  if( array[midPoint] < num ) --> only look at second half of the array
  if( array[midpoint] > num ) --> only look at first half of the array
  //recursively repeat until you arrive at your solution
  
}

thisOld(29, sortedAges) // returns true 

//Notes
 //There are a bunch of other checks that should go into this example for it to be truly functional, but not necessary for this explanation.
 //This solution works because our Array is sorted
 //Recursive solutions are often logarithmic
 //We'll get into recursion in another post!

O (n) – Timp liniar

Trebuie să te uiți la fiecare element din matrice sau listă pentru a îndeplini sarcina. Singur pentru bucle sunt aproape întotdeauna timp liniar. De asemenea, metode de matrice precum Index de sunt, de asemenea, timp liniar. Ești abstracționat de procesul de looping.

//The number of steps you take is directly correlated to the your input size

function addAges(array){
  var sum = 0;
  for (let i=0 ; i < array.length; i++){  //has to go through each value
    sum += array[i]
  }
 return sum;
}

addAges(sortedAges) //133

O (n²) – Timp quadratic

Cuibărit pentru bucle sunt timp pătratic, deoarece executați o operație liniară în cadrul unei alte operații liniare (sau n * n = n²).

//The number of steps you take is your input size squared

function addedAges(array){
  var addedAge = [];
    for (let i=0 ; i < array.length; i++){ //has to go through each value
      for(let j=i+1 ; j < array.length ; j++){ //and go through them again
        addedAge.push(array[i] + array[j]);
      }
    }
  return addedAge;
}

addedAges(sortedAges); //[ 46, 49, 51, 53, 51, 53, 55, 56, 58, 60 ]

//Notes
 //Nested for loops. If one for loop is linear time (n)
 //Then two nested for loops are (n * n) or (n^2) Quadratic!

O (2 ^ n) – Timp exponențial

Timpul exponențial este de obicei pentru situațiile în care nu știți atât de mult și trebuie să încercați orice combinație sau permutare posibilă.

//The number of steps it takes to accomplish a task is a constant to the n power

//Thought example
 //Trying to find every combination of letters for a password of length n

Ar trebui să faceți o analiză a complexității timpului oricând scrieți cod care trebuie să ruleze rapid.

Când aveți diverse rute pentru a rezolva o problemă, este cu siguranță mai înțelept să creați o soluție care funcționează mai întâi. Dar, pe termen lung, veți dori o soluție care să ruleze cât mai rapid și eficient posibil.

Pentru a vă ajuta cu procesul de rezolvare a problemelor, iată câteva întrebări simple de pus:

1. Rezolvă această problemă? da =>

2. Ai timp să lucrezi la asta

da => treceți la pasul 3

Nu => Reveniți la el mai târziu și treceți la pasul 6 pentru moment.

3. Acoperă toate cazurile de margine? da =>

4. Sunt complexitățile mele cât mai reduse?

Nu => rescrieți sau modificați într-o soluție nouă -> reveniți la pasul 1

da => treceți la pasul 5

5. Codul meu este uscat? da =>

6. Bucură-te!

Nu => Fă-l uscat, apoi bucură-te!

Analizați complexitatea timpului oricând și în orice moment încercați să rezolvați o problemă. Vă va face un dezvoltator mai bun în jurnal. Coechipierii și utilizatorii tăi te vor iubi pentru asta.

Din nou, majoritatea problemelor cu care vă veți confrunta ca programator – fie algoritmic, fie programatic – vor avea zeci, dacă nu sute de modalități de rezolvare. Ele pot varia în ceea ce privește modul în care rezolvă problema, dar toate rezolvă problema respectivă.

Ați putea lua decizii între a folosi seturi sau grafice pentru a stoca date. Ați putea decide dacă utilizați sau nu Angular, React sau Backbone pentru un proiect de echipă. Toate aceste soluții rezolvă aceeași problemă într-un mod diferit.

Având în vedere acest lucru, este greu de spus că există un singur răspuns „corect” sau „cel mai bun” la aceste probleme. Dar este posibil să spunem că există răspunsuri „mai bune” sau „mai rele” la o anumită problemă.

Folosind unul dintre exemplele noastre anterioare, ar putea fi mai bine să folosiți React pentru un proiect de echipă dacă jumătate din echipa dvs. are experiență cu acesta, deci va dura mai puțin timp pentru a începe și a funcționa.

Capacitatea de a descrie o soluție mai bună izvorăște de obicei dintr-o aparență de analiză a complexității timpului.

Pe scurt, dacă ai de gând să rezolvi o problemă, rezolvă-o bine. Și folosiți niște Big-O pentru a vă ajuta să aflați cum.

Iată o recapitulare finală:

  • O (1) – Timp constant: este nevoie de un singur pas pentru ca algoritmul să îndeplinească sarcina.
  • O (jurnal n) – Timpul logaritmic: Numărul de pași necesari pentru realizarea unei sarcini este redus cu un anumit factor cu fiecare pas.
  • Pe) – Timp liniar: numărul de pași necesari este direct legat (1 la 1).
  • O (n²) – Timp quadratic: Numărul de pași necesari pentru realizarea unei sarcini este pătrat de n.
  • O (C ^ n) – Exponențial: numărul de pași pe care îi parcurge pentru a realiza o sarcină este o constantă la puterea n (număr destul de mare).

Iată câteva resurse utile pentru a afla mai multe:

  • Wikipedia
  • Big O Cheat Sheet este o resursă excelentă, cu complexități algoritmice comune în timp și o reprezentare grafică. Verifică!