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

Оценка сложности алгоритма (Big O notation) — это способ описать, как время выполнения или потребление памяти алгоритма растёт с увеличением размера входных данных.

Примеры:

• O(1) — константная сложность (доступ к элементу массива по индексу).
• O(n) — линейная сложность (перебор массива).
• O(n²) — квадратичная сложность (вложенные циклы).

// O(n) — линейный поиск
function findElement(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

Нюансы:

• Big O описывает худший случай.
• Константы и меньшие степени игнорируются (O(2n) → O(n)).
• Полезен для сравнения алгоритмов, но не учитывает реальное время работы.