«Время — вор памяти». - Стивен Кинг.

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

Функция BakeCupcake (вкус, глазурь) {

1. Разогрейте духовку до 375F или 190C.

2. Сделайте формочки для маффинов из бумаги.

3. Взбить сливки, масло и сахар до пышности.

4. Добавьте яйца.

5. Добавляем муку (смешанную с разрыхлителем).

6. Добавьте ваниль.

7. Равномерно распределите по формам.

8. Выпекать 18 минут. Дайте остыть!

}

var Amazing = BakCupcake («Ваниль», правда);

Алгоритм, по сути, представляет собой серию шагов, предпринимаемых для достижения чего-то! Теперь мы можем установить связь между временной сложностью и алгоритмами. Время очень важно для разработчиков, когда дело доходит до рендеринга пользовательского опыта. Мы можем анализировать временную сложность, используя математически определенный подход, широко известный как нотация Big-O. Big-O разбивает алгоритм на серию шагов, чтобы мы могли алгебраически обобщить, сколько времени может потребоваться для завершения алгоритма. Давайте взглянем на пять общих категорий временной сложности:

  • Константа — O(n): для завершения алгоритма требуется всего один шаг.
  • Логарифмический — O(log n): количество шагов, которые нужно выполнить, уменьшается на некоторый коэффициент с каждым шагом.
  • Линейный — O(n): количество шагов напрямую связано (1:1).
  • Квадратичный — O(n²): количество шагов для выполнения задачи равно n в квадрате.
  • Экспоненциальный — O(C^n): количество шагов, которые необходимо выполнить, является константой в n-й степени.

*Данный размер ввода n

Очевидно, что временная сложность имеет решающее значение при создании функций в Javascript. Для незначительных входных данных может показаться, что их легко просмотреть, но когда размеры входных данных начинают увеличиваться, время, необходимое нашим алгоритмам для выполнения задачи, начинает нежелательно увеличиваться. Мы должны стремиться к постоянному времени (если наш алгоритм позволяет нам такую ​​возможность), так как это наиболее эффективная временная сложность.

Анализ временной сложности:

В настоящее время наиболее распространенной метрикой для расчета временной сложности является нотация Big O. При этом удаляются все постоянные коэффициенты, так что время работы можно оценить относительно N, поскольку N приближается к бесконечности. В общем, вы можете думать об этом так:

Пример (константа):

console.log("hello")

Выше у нас есть одно утверждение. Его временная сложность будет постоянной. Время выполнения оператора не изменится по отношению к N.

Пример (линейный):

for (int i = 0; i < N; i++) {
  console.log("hello")
}

Временная сложность приведенного выше алгоритма будет линейной. Время работы цикла прямо пропорционально N. Когда N удваивается, увеличивается и время работы.

Пример (квадратичный):

for (int i = 0; i < N; i++) {
  for (int i = 0; i < N; i++) {
    console.log("hello")
  }
}

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

Пример (логарифмический):

while (low <= high) {
  let middle = (low + high) / 2;
  if (target < data[middle]) {
    high = middle - 1;
  }
  else if (target > data[middle]) {
    low = middle + 1;
  }
  else {
    break;
  }
}

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