de Festus K. Yangani

Un ghid pentru începători pentru notația O mare

Ghid pentru incepatori la Big O Notation

Notarea O mare este o modalitate de a reprezenta cât timp va dura un algoritm să se execute. Acesta permite unui inginer software să determine cât de eficiente sunt diferitele abordări pentru rezolvarea unei probleme.

Iată câteva tipuri obișnuite de complexitate temporală în Big O Notation.

  • O (1) – Complexitatea timpului constant
  • O (n) – Complexitatea timpului liniar
  • O (log n) – Complexitatea timpului logaritmic
  • O (n ^ 2) – Complexitatea timpului quadratic

Sperăm că până la sfârșitul acestui articol veți putea înțelege elementele de bază ale Big O Notation.

O (1) – Timp constant

Algoritmii cu timp constant vor necesita întotdeauna aceeași cantitate de timp pentru a fi executați. Timpul de execuție al acestor algoritmi este independent de dimensiunea intrării. Un bun exemplu de timp O (1) este accesarea unei valori cu un index de matrice.

var arr = [ 1,2,3,4,5];
arr[2]; // => 3

Alte exemple includ: operațiile push () și pop () pe o matrice.

O (n) – Complexitatea timpului liniar

Un algoritm are o complexitate liniară a timpului dacă timpul pentru executarea algoritmului este direct proporțional cu dimensiunea de intrare n. Prin urmare, timpul necesar pentru a rula algoritmul va crește proporțional cu dimensiunea intrării n crește.

Un bun exemplu este găsirea unui CD într-un teanc de CD-uri sau citirea unei cărți, unde n este numărul de pagini.

Exemple din O (n) utilizează căutarea liniară:

//if we used for loop to print out the values of the arrays
for (var i = 0; i < array.length; i++) {  console.log(array[i]);}
var arr1 = [orange, apple, banana, lemon]; //=> 4 steps
var arr2 = [apple, htc,samsung, sony, motorola]; //=> 5 steps

O (log n) – Complexitatea timpului logaritmic

Un algoritm are o complexitate logaritmică a timpului dacă timpul necesar pentru a rula algoritmul este proporțional cu logaritmul mărimii de intrare n. Un exemplu este căutarea binară, care este adesea utilizată pentru a căuta seturi de date:

//Binary search implementationvar doSearch = function(array, targetValue) {    var minIndex = 0;    var maxIndex = array.length - 1;    var currentIndex;    var currentElement;        while (minIndex <= maxIndex) {        currentIndex = (minIndex + maxIndex) / 2 | 0;        currentElement = array[currentIndex];        if (currentElement < targetValue) {            minIndex = currentIndex + 1;        } else if (currentElement > targetValue) {            maxIndex = currentIndex - 1;        } else {            return currentIndex;        }    }    return -1;  //If the index of the element is not found.};
var numbers = [11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33];
doSearch(numbers, 23) //=>; 6

Alte exemple de complexitate logaritmică a timpului includ:

Example 1;
for (var i = 1; i < n; i = i * 2)  console.log(i);}
Example 2;
for (i = n; i >= 1; i = i/2) console.log(i);}

O (n ^ 2) – Complexitatea timpului cuadratic

Un algoritm are complexitate de timp pătratic dacă timpul până la execuție este proporțional cu pătratul dimensiunii de intrare. Un bun exemplu în acest sens este verificarea pentru a vedea dacă există duplicate într-un pachet de cărți.

Veți întâlni complexitatea timpului pătratic în algoritmi care implică iterații imbricate, cum ar fi imbricate pentru bucle. De fapt, buclele imbricate mai adânci vor avea ca rezultat O (n ^ 3), O (n ^ 4) etc.

for(var i = 0; i < length; i++) {     //has O(n) time complexity    for(var j = 0; j < length; j++) { //has O(n^2) time complexity      // More loops?    }}

Alte exemple de complexitate a timpului pătratic includ sortarea cu bule, sortarea prin selecție și sortarea prin inserție.

Acest articol zgârie doar suprafața Big O Notation. Dacă doriți să înțelegeți mai multe despre Big O Notation, vă recomand să verificați Big-O Cheat Sheet.