У всех алгортимов есть 2 главные характеристики:

  1. Количество необходимой памяти.
  2. Время выполнения.

Их используют для того, чтобы сравнивать алгоритмы между собой. Одни алгоритмы работают быстрее, но требуют больше памяти, а другие наоборот.

Для большинства алгоритмов время выполнения и количество памяти нельзя выразить одним числом. Чем больше элементов будет во входящем массиве, тем дольше будут выполняться поиск и сортировка.

Для описания эффективности алгоритмов придумали нотацию Big-O.

Постоянная сложность - О(1)

Самый эффективный алгоритм в теории работает за постоянное время и расходует постоянное количество памяти. Как ни увеличивай объем входящих данных, сложность алгоритма не повысится. Эффективность (или сложность) такого алгоритма называют константным и записывают как O(1).

Пример алгоритма с постоянной сложностью:

const getArrayElement = (arr, i) => arr[i];

На вход получаем массив arr и индекс i. Возвращаем элемент массива на позиции i.

Скорость выполнения и объем требуемой памяти этого алгоритма не зависит от длины входящего массива, поэтому сложность считается постоянной.

Линейная сложность - O(n)

Сложность многих алгоритмов растет прямо пропорционально изменению количества входящих данных.

Хороший пример - линейный поиск:

const findArrayElement = (arr, x) => {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === x) {
      return i;
    }
  }
  
  return -1;
}

Если поиск в массиве из 10 элементов занимает 5 секунд, то в массиве из 100 элементов мы будем искать 100 секунд. В 10 раз дольше.

Такую сложность (эффективность) называют линейной и записывают как О(n).

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

Квадратичная сложность - O(n^2^)

Простые алгоритмы сортировки, такие как сортировка пузырьком или сортировка выбором имеют сложность О(n^2^).

Это не очень эффективно. При росте длины массива в 10 раз, время выполнения алгоритма увеличится в 10^2^ (в 100) раз!

Так происходит из-за того, что в алгоритме используется вложенный цикл. Сложность одного прохода мы оцениваем как O(n). Но проходим мы его не один раз, а **n **раз. Поэтому и получается сложность O(n * n) = O(n^2^).

Логарифмическая сложность - O(log n)

Алгоритмы, которые на каждой итерации могут сократить количество анализируемых данных имеют логарифмическую сложность - O(log n).

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