Ръководство за начинаещи за Big O Notation

Big O Notation е начин да се представи колко време ще отнеме даден алгоритъм за изпълнение. Той дава възможност на софтуерен инженер да определи колко ефективни са различните подходи за решаване на проблем.

Ето някои често срещани типове времеви сложности в Big O Notation.

  • O (1) - Постоянна сложност във времето
  • O (n) - Линейна времева сложност
  • O (log n) - Логаритмична времева сложност
  • O (n ^ 2) - Квадратична времева сложност

Надяваме се, че в края на тази статия ще можете да разберете основите на Big O Notation.

O (1) - Постоянно време

Алгоритмите с постоянно време винаги ще отнемат еднакво време за изпълнение. Времето за изпълнение на този алгоритъм не зависи от размера на входа. Добър пример за O (1) време е достъпът до стойност с индекс на масив.

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

Други примери включват: push () и pop () операции върху масив.

O (n) - Линейна времева сложност

Алгоритъмът има линейна времева сложност, ако времето за изпълнение на алгоритъма е право пропорционално на размера на входа n . Следователно времето, необходимо за стартиране на алгоритъма, ще се увеличи пропорционално с увеличаване на размера на входа n .

Добър пример е намирането на CD в купчина компактдискове или четенето на книга, където n е броят на страниците.

Примери в O (n) използва линейно търсене:

//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) - Логаритмична времева сложност

Алгоритъмът има логаритмична времева сложност, ако времето, необходимо за стартиране на алгоритъма, е пропорционално на логаритъма на входния размер n . Пример за това е двоично търсене, което често се използва за търсене в набори от данни:

//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) { 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

Други примери за логаритмична времева сложност включват:

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) - Квадратична времева сложност

Алгоритъмът има квадратична времева сложност, ако времето за изпълнение е пропорционално на квадрата на входния размер. Добър пример за това е проверката дали има дубликати в тесте карти.

Ще срещнете квадратична времева сложност в алгоритми, включващи вложени итерации, като например вложени за цикли. Всъщност по-дълбоко вложените цикли ще доведат до O (n ^ 3), O (n ^ 4) и т.н.

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? }}

Други примери за квадратична времева сложност включват сортиране на балончета, сортиране по избор и сортиране при вмъкване.

Тази статия само надрасква повърхността на Big O Notation. Ако искате да разберете повече за Big O Notation, препоръчвам да разгледате Big-O Cheat Sheet.