Если двум идентично написанным функциям передаются два разных массива, один из которых содержит один элемент, а другой - три тысячи элементов, выполнение какой функции займет больше времени? На сколько?
Учтите следующее:
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), поскольку константа становится все более и более нерелевантной, поскольку вход растет.
На сегодня все, ребята!