AKA сложность пространства-времени

Что такое сложность времени?
Итак, ваша программа работает, но работает слишком медленно. Или, может быть, ваш милый маленький код отлично работает, но работает не так быстро, как другой, более длинный. Добро пожаловать в Big-O Time Complexity, где повторение - враг, а массивы правят безраздельно. Шучу… вроде. Обозначение Big-O - распространенное средство описания производительности или сложности алгоритма в компьютерных науках. С практической точки зрения, он используется как барометр для проверки эффективности вашей функции и того, можно ли ее улучшить. Сложность времени станет важным аспектом вашей среды разработки по мере того, как вы продолжите прогрессировать в учебе. В конце концов, вы сможете проанализировать свою программу и определить, какие программы относятся к какой временной сложности (постоянная, линейная, квадратичная, экспоненциальная, логарифмическая). В этом руководстве мы разберем основы сложности времени, чтобы лучше понять, как они выглядят в вашем коде и в реальной жизни.

O (1) - Постоянное время:
Постоянная сложность времени описывает алгоритм, который всегда будет выполняться в одно и то же время (или пространство) независимо от размера набора входных данных. В JavaScript это может быть так же просто, как доступ к определенному индексу в массиве:

var array = [1, 2, 3, 4, 5];
array[0] // This is a constant time look-up
--------------------------------------------------------------------var removeLastElement = function(array) {
  var numberOfElementsToRemove = 2;
while (numberOfElementsToRemove > 0) {
    array.pop();
  }
}; //This will also have a constant time look-up since the function 
   //is only looking at a specific reference point within the array.

Не имеет значения, имеет ли массив 5 или 500 индексов, поиск определенного места в массиве займет одинаковое количество времени, поэтому функция имеет постоянный поиск по времени.

Точно так же, если бы у меня была колода карт, и я попросил бы вас удалить первую любую карту наугад, вы могли бы просто взять карту из колоды, не просматривая всю колоду. Это постоянный поиск по времени.

O (N) - линейное время:
линейное время: сложность описывает алгоритм или программу, сложность которых будет расти прямо пропорционально размеру входных данных. Как показывает опыт, лучше всего попытаться сохранить работу ваших функций ниже или в этом диапазоне временной сложности, но, очевидно, это не всегда будет возможно.

var numberRange = function(array) {
  for (var i = 1; i < array.length; i++) {
    console.log(array[i]);
  }
}; //This will have a linear time look-up since the function is
   //looking at a every index in the array once.

В этом примере время поиска напрямую связано с размером нашего ввода, потому что мы будем просматривать каждый элемент в массиве. Другими словами, чем больше ввод, тем больше времени требуется для выполнения функции. Конечно, если бы у массива был только 1 индекс (т.е. array.length === 1), тогда функция имела бы постоянный поиск по времени.

А теперь вернемся к нашей аналогии с колодой карт. Если бы у меня была колода карт, и я хотел бы, чтобы вы выбрали конкретную карту (скажем, 10 центов). Вам придется просматривать каждую карту, пока вы не найдете ее. Конечно, есть вероятность, что это будет первая карта в колоде, но это маловероятно. А теперь подумайте, была ли колода карт заполнена сотнями других карт, отличных от 10❤. Ваш поиск напрямую зависит от размера колоды карт. Это пример линейной сложности.

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

//NOTE: This function is not an example of a Binary Search Tree
var partialRange = function(array) {
  for (var i = 1; i < array.length; i = i * 2) {
    console.log(array[i]);
  }
}; //This will have a logarithmic time look-up since the function is
   //looking at only searching through part of the array.

В приведенной выше функции мы регистрируем числа до тех пор, пока не будет передана длина массива. Однако мы видим, что наша функция будет регистрировать числа только с определенным интервалом. Поскольку мы будем повторять поиск с постоянным временем для нескольких частей массива, наша функция не будет иметь поиск с постоянным временем. Также следует отметить, что, поскольку наша функция не проходит через все индексы в массиве, у нее не будет линейного поиска по времени.

Используя нашу аналогию с колодой карт, предположим, что наши карты упорядочены в порядке возрастания к убыванию, при этом колода разделена пополам: одна стопка содержит трефы и пики, а другая - карты сердец и ромбов. Теперь, если я попрошу вас вытащить 10❤, вы можете с уверенностью заключить, что карта должна быть во второй стопке, поскольку именно там находятся карты бубны и червы. Кроме того, вы знаете, что карта должна быть только с сердечками, поэтому вы разделяете колоду, чтобы искать только сердечки. Поскольку вы будете искать 10❤, вы можете с уверенностью предположить, что нижняя половина колоды не имеет значения (поскольку колода уже отсортирована). Вы можете продолжать разделять оставшиеся карты, пока в конце концов не найдете 10❤. Вам не нужно было перебирать каждую карту, чтобы найти ее, но это было не так просто, как просто взять случайную карту. Это пример логарифмической сложности времени.

O (N²) - квадратичное время:
Квадратичное время сложности представляет собой алгоритм, производительность которого прямо пропорциональна квадрату размера входного набора данных (подумайте о линейном, но возведенном в квадрат). В наших программах эта временная сложность будет возникать всякий раз, когда мы вкладываем несколько итераций в наборы данных.

var hasDuplicates = function(array) {
  for (var i = 0; i < array.length; i++) {
    var item = array[i];
    if (array.slice(i + 1).indexOf(item) !== -1) {
      return true;
    }
  }
  return false;
}; //This will have a quadratic time look-up since the function is
   //looking at a every index in the array twice.

Эта функция - отличный пример того, как легко пройти через массив дважды, не используя два цикла for. Из первой части ясно, что наша функция будет выполнять поиск в массиве хотя бы один раз, но разница заключается в выражении if. Здесь мы выполняем еще один поиск в массиве с помощью собственного метода indexOf. При этом мы дважды обходим один и тот же массив при каждом поиске, создавая квадратичную временную сложность.

Вернемся к нашей колоде карт. Допустим, вы выбрали первую карту в колоде и как удалить все карты с тем же номером. Вам придется искать в колоде, удаляя дубликаты в каждой точке. Убедившись, что все дубликаты удалены, вы продолжаете делать то же самое для второй карты, третьей и так далее, пока не дойдете до конца колоды. Это пример квадратичной временной сложности.

O (2 ^ N) - экспоненциальное время
Экспоненциально-временная сложность обозначает алгоритм, рост которого удваивается с каждым добавлением к входному набору данных. Если вам известны другие модели экспоненциального роста, это работает примерно так же. Временная сложность начинается очень мелко, и до конца возрастает с постоянно увеличивающейся скоростью.

var fibonacci = function(number) {
  if (number <= 1) return number;
  return Fibonacci(number - 2) + Fibonacci(number - 1);
}; //This will have an exponential time look-up since the function 
   //is looking at a every index an exponential number of times.

Числа Фибоначчи - отличный способ попрактиковаться в понимании рекурсии. Хотя есть способ сделать функцию Фибоначчи более короткой временной сложностью, в этом случае мы будем использовать двойной рекурсивный метод, чтобы показать, как она имеет экспоненциальную временную сложность. Короче говоря, рекурсивное создание экземпляра будет проходить через каждое число от числа до нуля. Он будет делать это дважды (один раз для каждого рекурсивного вызова), пока не достигнет базового случая оператора if. Поскольку количество рекурсивных вызовов напрямую связано с числом ввода, легко увидеть, как это время поиска быстро вырастет из-под контроля.

Если вы все еще ищете краткую справочную информацию, которая поможет вам лучше разобраться в этом (или в любой другой временной сложности), я настоятельно рекомендую проверить Шпаргалку Big-O . Надеюсь, это помогло!