Посібник для початківців з позначення Big O

Позначення Big O - це спосіб представити, скільки часу буде виконуватися алгоритмом. Це дозволяє інженеру-програмісту визначити, наскільки ефективні різні підходи до вирішення проблеми.

Ось декілька поширених типів часових складностей у 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 .

Хорошим прикладом є пошук компакт-диска в стосі компакт-дисків або читання книги, де 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. Якщо ви хочете дізнатись більше про Big O Notation, я рекомендую перевірити шпаргалку Big-O.