«Время — вор памяти». - Стивен Кинг.
У каждого есть время на их стороне, так что давайте погрузимся в царство временной сложности. Для начала давайте кратко определим временную сложность как: «количество времени, в течение которого алгоритм работает как функция, по отношению к размеру входных данных». Теперь вам может быть интересно, что такое алгоритм. Вот простой пример алгоритма, с которым вы, возможно, знакомы:
Функция 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. Это связано с тем, что алгоритм делит данные пополам на каждой итерации.