Если двум идентично написанным функциям передаются два разных массива, один из которых содержит один элемент, а другой - три тысячи элементов, выполнение какой функции займет больше времени? На сколько?

Учтите следующее:

let array1 = [1];
let array2 = [1, 2, <--digits here-->, 3000];
function alertFirstElement(array){
  alert(array[0]);
}
alertFirstElement(array1);
alertFirstElement(array2);

Как мы можем классифицировать количество времени, необходимое для завершения работы вышеуказанной функции? Будут ли входы разного размера работать по-разному? Что, если мы заменим эту функцию вышеупомянутой?

function alertAllElements(array){
  array.forEach(element => alert(element));
};

Независимо от того, сколько элементов содержится во входных данных первой функции, она всегда будет работать с один раз. Количество срабатываний второй функции, однако, напрямую зависит от размера получаемых ею входных данных. Время выполнения этих двух функций можно сравнить, представив их в нотации Big O как O (1) и O (n).

Короче говоря, нотация Big O используется для классификации алгоритмов по тому, насколько быстро время их выполнения растет по сравнению с их вводом.

Нотация Big O не рассчитывает точное время выполнения алгоритма (например, «эта функция завершит работу через 400 мс»), а скорее скорость, с которой время ее выполнения увеличивается при увеличении размера входных данных. .

Давайте углубимся немного глубже и рассмотрим некоторые алгоритмы в постоянном времени, линейном времени, квадратичном времени и логарифмическом времени.

O (1): «Постоянное время»

Давайте рассмотрим пример, приведенный в начале этой статьи:

let array1 = [1];
let array2 = [1, 2, <--digits here-->, 3000];
function alertFirstElement(array){
  alert(array[0]);
}
alertFirstElement(array1);
alertFirstElement(array2);

Эта функция имеет постоянное время, которое обозначается как O (1), или «заказ один». Другими словами, время, необходимое для выполнения этой функции, всегда будет постоянным, независимо от размера входных данных.

O (n): «Линейное время»

Функция будет классифицироваться как «порядок n» или O (n), если время ее выполнения увеличивается в соотношении 1: 1 к ее Вход. Рассмотрим функцию, которая просматривает массив в поисках первого индекса указанного значения:

function indexOf(array, target){
  for(let i = 0; i < array.length; i++){
    if(array[i] === target){
      return i;
    }
  }
  return -1;
};
let array = ["all", "cows", "eat", "grass"];
indexOf(array, "cows"); //will return 1

Поскольку нотация Big O работает в наихудших сценариях, предполагается, что цель находится в конечном индексе входного массива. Следовательно, для массива длиной 4 функция должна перебирать все 4 элемента, чтобы найти свою цель.

O (n²): «квадратичное время»

Функция в квадратичном времени, или O (n²), выполняется n раз для каждого из n элементы во входных данных.

Рассмотрим цикл внутри цикла:

function multiplicationTable(array){
  let table = [];
  for(let x = 0; x < array.length; x++){
    let row = [];
    for(let y = 0; y < array.length; y++){
      row.push(array[x] * array[y]);
    }
    table.push(row);
  }
  return table;
}
console.log(multiplicationTable([1, 2, 3]));

O (log n): «Логарифмическое время»

Наиболее успешные алгоритмы сортировки и поиска для больших наборов данных выполняются за логарифмическое время, или O (log n). Эти алгоритмы, такие как быстрая сортировка или двоичный поиск, работают, разрезая коллекцию пополам и затем рекурсивно вызывая себя на каждой половине. В худшем случае эта операция повторяется по массиву log n раз.

Хотя математика этих операций выходит за рамки данной статьи, я скоро опубликую подробное объяснение механики логарифмической сортировки и алгоритмов поиска.

Прежде чем закончить, я хотел бы высказать последнее замечание: нотация Big O не использует константы. Поскольку размер входных данных приближается к бесконечности, умножение его на n имеет убывающий эффект. Следовательно, O (2n) упрощается до O (n), поскольку константа становится все более и более нерелевантной, поскольку вход растет.

На сегодня все, ребята!