Как оценить сложность по памяти для алгоритма, работающего с массивом?

Что такое сложность по памяти

Сложность по памяти (space complexity) описывает, сколько дополнительной памяти требуется алгоритму в зависимости от размера входных данных. Она измеряется в терминах Big O notation, например O(1), O(n), O(n²). Для массивов важно понимать, что сам массив уже занимает память, но нас интересует именно дополнительная память, которую создаёт алгоритм.

Как оценивать для массивов

Если алгоритм работает с исходным массивом без создания копий и использует только несколько переменных, сложность будет O(1). Если создаётся новый массив того же размера, сложность O(n). Если создаётся двумерный массив размером n×n, то O(n²). Также нужно учитывать рекурсивные вызовы: каждый вызов добавляет кадр в стек, поэтому глубина рекурсии влияет на память.

Примеры

// O(1) — только переменная для суммы
function sum(arr) {
  let total = 0;
  for (let i = 0; i < arr.length; i++) {
    total += arr[i];
  }
  return total;
}

// O(n) — создаётся новый массив
function double(arr) {
  const result = [];
  for (let i = 0; i < arr.length; i++) {
    result.push(arr[i] * 2);
  }
  return result;
}

// O(n) — рекурсия глубиной n
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

Практическое применение

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

Итог: всегда оценивайте дополнительную память, а не только время. Для массивов чаще всего встречаются O(1) и O(n), но в сложных алгоритмах могут быть и O(n²). Это помогает предсказать поведение программы при росте входных данных.