Как оценить сложность алгоритма

Оценка сложности алгоритма выполняется с помощью Big O нотации, которая описывает, как растёт время выполнения или потребление памяти при увеличении входных данных.

Основные типы сложности:

• O(1) – константная (доступ к элементу массива)
• O(log n) – логарифмическая (бинарный поиск)
• O(n) – линейная (перебор массива)
• O(n log n) – линейно-логарифмическая (быстрая сортировка)
• O(n²) – квадратичная (вложенные циклы)
• O(2ⁿ) – экспоненциальная (рекурсивный Фибоначчи)

Пример:

// O(n) – линейная сложность
function sumArray(arr) {
  let sum = 0;
  for (let num of arr) { // Один цикл → O(n)
    sum += num;
  }
  return sum;
}

// O(n²) – квадратичная сложность
function findDuplicates(arr) {
  let duplicates = [];
  for (let i = 0; i < arr.length; i++) { // Вложенный цикл → O(n²)
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) duplicates.push(arr[i]);
    }
  }
  return duplicates;
}

Важно: Big O оценивает худший сценарий и игнорирует константы (O(2n) → O(n)).