Сложность алгоритмов - это ключевой аспект при проектировании и создании веб-приложений, особенно при работе с большим объемом данных или выполнении вычислительно сложных операций. Понимание, как оценивать сложность алгоритмов, помогает принимать обоснованные решения в выборе алгоритмов и структур данных, а также оптимизировать производительность своих приложений.
Сейчас мы рассмотрим, почему знание сложности алгоритмов является важным навыком для разработчика, какие методы используются для оценки сложности, и какие практические применения можно найти для этого знания при создании веб-приложений. На тему сложности алгоритмов часто задаются вопросы на техническом собеседовании.
Пример
Давайте представим, что у вас есть интернет-магазин, на котором пользователи могут искать продукты по разным параметрам, таким как цена, бренд, категория и другие фильтры.
Ваша задача - обеспечить быстрый и удобный поиск для пользователей.
Если вы не учтете сложность алгоритмов, то при реализации поиска вы можете выбрать неоптимальный алгоритм, который будет медленно обрабатывать запросы пользователей при большом количестве товаров. Например, вы можете реализовать поиск, который каждый раз просматривает все товары и сравнивает их с запросом пользователя.
Однако, если вы знаете сложность алгоритмов, то сможете выбрать более эффективный алгоритм для поиска, такой как бинарный поиск или хэш-таблицы. Эти алгоритмы имеют лучшую производительность и работают намного быстрее, даже если у вас есть большой каталог товаров.
Таким образом, знание сложности алгоритмов позволяет вам оптимизировать функциональность вашего интернет-магазина и обеспечить пользователям быстрый и удобный поиск, что может существенно повысить уровень удовлетворенности клиентов и увеличить конверсию.
Big O
Чтобы сравнивать алгоритмы по сложности сначала мы должны узнать что такое Big O.
Big O - это термин из области анализа сложности алгоритмов и структур данных в информатике. Он используется для оценки верхней границы (наихудшего случая), временной сложности алгоритма.
Простыми словами Big O показывает как будет меняться производительность алгоритма в зависимости от роста входящих данных.
Если мы будем увеличивать количество входящих данных, то у нас может расти количество операций и время за которое выполнится алгоритм. Так же может расти количество памяти используемой данным алгоритмом для обработки входного объема данных. Big O будет показывать скорость роста времени исполнения алгоритма.
Big O называется так из-за того, что в математике "O" используется для обозначения "order of" (порядка) и позволяет сравнивать функции роста. Он представляет собой математическую нотацию, которая описывает, как алгоритм будет выполняться в наихудшем случае, исходя из размера входных данных.
- Примеры нотаций Big O
- O(1): Константная сложность. Время выполнения алгоритма не зависит от размера входных данных. Например, доступ к элементу массива по индексу.
- O(log n): Логарифмическая сложность. Время выполнения алгоритма растет медленно с увеличением размера входных данных. Например, бинарный поиск в отсортированном массиве.
- O(n): Линейная сложность. Время выполнения алгоритма пропорционально размеру входных данных. Например, просмотр всех элементов в массиве.
- O(n log n): Линейно-логарифмическая сложность. Время выполнения алгоритма растет быстрее, чем линейно, но медленнее, чем квадратично. Например, сортировка слиянием (Merge Sort).
- O(n^2): Квадратичная сложность. Время выполнения алгоритма зависит от квадрата размера входных данных. Например, сортировка пузырьком (Bubble Sort).
- O(n^3): Кубическая сложность. Время выполнения алгоритма зависит от размера входных данных в кубе. Например, алгоритмы, которые имеют три вложенных цикла, такие как некоторые методы многомерной обработки данных.
- O(n!): Факториальная сложность. Это самая высокая степень роста времени выполнения алгоритма. Время выполнения алгоритма растет факториально от размера входных данных. Этот тип сложности встречается, например, при переборе всех возможных комбинаций элементов, что делает его чрезвычайно неэффективным для больших значений n.
- Другие обозначения сложности алгоритмов
Кроме обозначения "Big O", существуют другие обозначения для оценки сложности алгоритмов.
Вот несколько наиболее распространенных обозначений:
- Big Theta (Θ): Big Theta также оценивает верхнюю и нижнюю границы временной сложности алгоритма, но описывает точную сложность, а не только наихудший случай, как Big O. Θ(f(n)) обозначает, что время выполнения алгоритма ограничено функцией f(n) как сверху, так и снизу.
- Big Omega (Ω): Big Omega оценивает нижнюю границу временной сложности алгоритма. Ω(f(n)) говорит о том, что алгоритм выполнится не быстрее, чем функция f(n).
- Little O (o): Little O представляет собой верхнюю границу, которая строже, чем Big O. Если f(n) является o(g(n)), это означает, что время выполнения алгоритма ограничивается функцией g(n), но алгоритм работает быстрее, чем g(n).
- Little Omega (ω): Little Omega представляет собой нижнюю границу, которая строже, чем Big Omega. Если f(n) является ω(g(n)), это означает, что алгоритм работает медленнее, чем g(n), но не медленнее, чем f(n).
Эти обозначения помогают более точно определить сложность алгоритма и учитывать как наихудший, так и лучший случай его работы. Когда разработчики анализируют алгоритмы, они могут использовать Big O, Big Theta, Big Omega, Little O и Little Omega в зависимости от конкретного контекста и требований задачи.
Мы уделим внимание именно Big O, так как это обозначение используется чаще всего.
Константная Сложность O(1)
O(1) называют константной сложностью.
Оценка временной сложности O(1) означает, что алгоритм имеет постоянную сложность.
Под n мы будем иметь ввиду размер входящих данных.
В JavaScript чаще всего мы храним набор данных в массивах.
Размер массива, то есть его значение свойства length и будет значение n.
При константной сложности вне зависимости от размера входных данных (n), время выполнения алгоритма остается постоянным и не зависит от объема данных.
Это самый быстрый и эффективный вид временной сложности.
Примеры алгоритмов с оценкой временной сложности O(1):
- Доступ к элементу в массиве по индексу. Например, если у вас есть массив с данными, вы можете мгновенно получить доступ к элементу массива, указав его индекс, независимо от размера массива.
- Вставка или удаление элемента в конец списка (очереди) фиксированной длины. В этом случае операция выполняется быстро и не зависит от количества элементов в списке.
Оценка временной сложности O(1) является идеальной с точки зрения производительности. Однако в реальных задачах она не всегда достижима, и в большинстве случаев оценка временной сложности будет выше.
Давайте рассмотрим эту сложность на примере:
function getLastElement(arr) {
return arr[arr.length - 1 ]
}
Функция getLastElement имеет временную сложность O(1) потому, что она выполняет одну операцию - получение последнего элемента массива arr.
Независимо от размера массива, функция всегда выполняет одно действие, поэтому ее сложность остается постоянной и равной O(1). Это означает, что время выполнения функции не зависит от количества элементов в массиве и всегда будет быстрым и постоянным.
Линейная Сложность O(n)
O(n) называют линейной сложностью.
Линейный рост - это понятие, которое описывает зависимость между двумя величинами, при которой одна величина увеличивается пропорционально увеличению другой.
Оценка временной сложности O(n) означает, что время выполнения алгоритма растет линейно с увеличением размера входных данных.
function findMax(arr) {
let max = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
В этом примере findMax ищет максимальное значение в массиве arr.
Алгоритм начинает с предположения, что первый элемент массива (arr[0]) является максимальным, а затем линейно (то есть по одному элементу) перебирает остальные элементы, сравнивая каждый с текущим максимальным. Сложность этого алгоритма O(n), так как время выполнения растет линейно с увеличением количества элементов в массиве arr.
При линейном росте при увеличении размера входных данных вдвое, то время выполнения алгоритма также увеличится примерно вдвое. Если увеличите размер данных в 10 раз, то время выполнения увеличится приблизительно в 10 раз, и так далее.
Линейный рост характерен для алгоритмов, которые выполняют постоянное количество операций для каждого элемента входных данных.
Логарифмическая Сложность O(log n)
O(log n) называют логарифмической сложностью.
Оценка временной сложности O(log n) означает, что время выполнения алгоритма увеличивается логарифмически с увеличением размера входных данных (n). Другими словами, алгоритм становится медленнее, но не линейно, а медленнее в соответствии с логарифмической функцией.
Пример алгоритма с оценкой временной сложности O(log n) - бинарный поиск. В этом алгоритме на каждом шаге половина данных отсекается, и поиск продолжается в оставшейся половине. Это означает, что при увеличении размера входных данных вдвое, бинарный поиск требует всего одного дополнительного шага.
Таким образом, алгоритмы с оценкой временной сложности O(log n) эффективны и быстры при работе с большими объемами данных, так как их производительность ухудшается медленно с увеличением размера данных.
Пример функции бинарного поиска на JavaScript, которая имеет сложность O(log n):
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid; // элемент найден
} else if (arr[mid] < target) {
left = mid + 1; // искать в правой половине
} else {
right = mid - 1; // искать в левой половине
}
}
return -1; // элемент не найден
}
Бинарный поиск ищет значение в отсортированном массиве, разделяя его пополам на каждой итерации. Поиск начинается с середины массива. Если значение, которое мы ищем, больше среднего элемента, поиск продолжается в правой половине массива. Если оно меньше, то в левой. Таким образом, на каждой итерации мы уменьшаем область поиска примерно в два раза, что обеспечивает логарифмическую сложность O(log n).
Квадратичная Сложность O(n^2)
O(n^2) означает квадратичную сложность алгоритма, где время выполнения растет пропорционально квадрату размера входных данных. Это часто возникает в алгоритмах с вложенными циклами, когда каждый элемент первого списка обрабатывается с каждым элементом второго списка.
Вот пример простого алгоритма с квадратичной сложностью, который ищет сумму всех пар элементов в массиве:
function sumOfPairs(arr) {
let sum = 0;
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
sum += arr[i] + arr[j];
}
}
return sum;
}
const myArray = [1, 2, 3, 4];
console.log(sumOfPairs(myArray)); // 80
Этот код имеет два вложенных цикла, каждый из которых проходится по всему массиву. Количество операций в циклах равно n * n, где n - это длина массива. Это приводит к квадратичной сложности O(n^2), что может сделать его неэффективным для больших массивов из-за большого количества операций, выполняемых на каждый элемент.
Кубическая Сложность O(n^3)
Cложность O(n^3) означает, что время выполнения алгоритма увеличивается кубически по размеру входных данных. Это часто встречается в алгоритмах, где есть три вложенных цикла или операции, каждая из которых выполняется пропорционально кубу размера входных данных.
Вот пример алгоритма с кубической сложностью, который умножает две матрицы:
function multiplyMatrices(matrix1, matrix2) {
let result = [];
const m = matrix1.length;
const n = matrix2[0].length;
const p = matrix2.length;
for (let i = 0; i < m; i++) {
result[i] = [];
for (let j = 0; j < n; j++) {
result[i][j] = 0;
for (let k = 0; k < p; k++) {
result[i][j] += matrix1[i][k] * matrix2[k][j];
}
}
}
return result;
}
const matrixA = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
];
const matrixB = [
[9, 8, 7],
[6, 5, 4],
[3, 2, 1]
];
console.log(multiplyMatrices(matrixA, matrixB));
Этот алгоритм умножения матриц имеет три вложенных цикла: первый проходится по строкам первой матрицы, второй по столбцам второй матрицы, а третий - по общим элементам для умножения. Количество операций равно n * n * n, где n - это размер матрицы. Это приводит к кубической сложности O(n^3). Такой подход может стать неэффективным для больших матриц из-за большого количества операций, которые необходимо.
Экспоненциальная Сложность O(2^n)
Сложность O(2^n) относится к экспоненциальной сложности, где время выполнения алгоритма увеличивается экспоненциально по мере увеличения размера входных данных. Это часто встречается в алгоритмах, которые решают проблемы методом "разделяй и властвуй" или используют рекурсию без оптимизации.
Примером алгоритма с экспоненциальной сложностью может служить рекурсивное вычисление чисел Фибоначчи:
function fibonacci(n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
console.log(fibonacci(5)); // 5
console.log(fibonacci(10)); // 55
console.log(fibonacci(20)); // 6765
Этот код использует рекурсию для вычисления чисел Фибоначчи. Однако каждый раз, когда вызывается функция fibonacci, она порождает два дополнительных вызова, что приводит к экспоненциальному увеличению количества вызовов функций с увеличением n.
Для больших значений n такой подход становится очень неэффективным из-за огромного числа повторных вычислений. Экспоненциальная сложность обычно не является оптимальным решением из-за своей высокой вычислительной нагрузки при увеличении размера входных данных.
Факториальная Сложность O(n!)
Сложность O(n!) относится к факториальной сложности, где время выполнения алгоритма растет пропорционально факториалу размера входных данных. Факториал - это произведение всех положительных целых чисел от 1 до n.
Пример алгоритма с факториальной сложностью может быть перебор всех перестановок элементов массива:
function permute(arr) {
function swap(a, b) {
const temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
function generate(n) {
if (n === 1) {
console.log(arr);
} else {
for (let i = 0; i < n - 1; i++) {
generate(n - 1);
if (n % 2 === 0) {
swap(i, n - 1);
} else {
swap(0, n - 1);
}
}
generate(n - 1);
}
}
generate(arr.length);
}
const myArray = [1, 2, 3];
permute(myArray);
Этот код создает все возможные перестановки элементов массива путем рекурсивного генерирования всех возможных комбинаций. Количество операций, необходимых для генерации всех перестановок, равно факториалу длины массива. Например, для массива из 3 элементов (как в примере выше) будет 3! = 3 * 2 * 1 = 6 перестановок.
Такой алгоритм обладает очень высокой вычислительной сложностью и может стать практически неиспользуемым для больших входных данных из-за огромного числа операций, которые необходимо выполнить.
График Сложностей Алгоритмов
Посмотрите на этот график. На нем сразу видно различия между скоростью роста различных сложностей.
Source: Habr