Какова сложность алгоритмов глубокого копирования больших объектов?

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

Сложность по времени

Если обозначить n как общее количество узлов (свойств, элементов массивов, примитивов) в графе объекта, то алгоритм должен посетить каждый узел ровно один раз. Значит, временная сложность — O(n). Константа зависит от способа обхода: рекурсия, стек, structuredClone или сериализация через JSON.

Сложность по памяти

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

Особые случаи

• Циклические ссылки: без отслеживания посещённых объектов рекурсия уйдёт в бесконечность.
• Специальные типы: Date, Map, Set, RegExp, ArrayBuffer требуют отдельной логики копирования.
• Функции и DOM-узлы обычно не копируются глубоко.

Пример на JavaScript

function deepClone(obj, seen = new WeakMap()) {
  if (obj === null || typeof obj !== 'object') return obj;
  if (seen.has(obj)) return seen.get(obj);

  const clone = Array.isArray(obj) ? [] : {};
  seen.set(obj, clone);

  for (const key of Object.keys(obj)) {
    clone[key] = deepClone(obj[key], seen);
  }
  return clone;
}

const source = { a: 1, b: { c: [1, 2, 3] } };
const copy = deepClone(source);
copy.b.c.push(4);
console.log(source.b.c); // [1, 2, 3]

В современном JavaScript часто используют встроенный structuredClone, который корректно обрабатывает циклы и многие типы, но всё равно имеет сложность O(n).

Итог: глубокое копирование линейно по времени и памяти относительно размера структуры, поэтому на очень больших объектах оно может быть дорогим. Применяйте его, когда нужна полная изоляция данных, а для больших структур рассмотрите иммутабельные подходы или структурное разделение (persistent data structures).