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

Анализ сложности алгоритма пересечения двух массивов

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

1. Наивный подход (двойной цикл)

Самый простой, но наименее эффективный метод — сравнение каждого элемента первого массива с каждым элементом второго.

function intersectionNaive(arr1, arr2) {
  const result = [];
  for (let i = 0; i < arr1.length; i++) {
    for (let j = 0; j < arr2.length; j++) {
      if (arr1[i] === arr2[j]) {
        result.push(arr1[i]);
        break; // чтобы избежать дубликатов
      }
    }
  }
  return result;
}

• Временная сложность: O(n*m), где n и m — длины массивов
• Пространственная сложность: O(min(n, m)) в худшем случае (когда один массив полностью содержится в другом)
• Недостатки: Крайне неэффективно для больших массивов

2. Использование хэш-таблицы (объекта/Set)

Более оптимальный подход, особенно когда порядок элементов не важен:

function intersectionHash(arr1, arr2) {
  const map = {};
  const result = [];
  
  // Заполняем хэш-таблицу элементами первого массива
  for (let i = 0; i < arr1.length; i++) {
    map[arr1[i]] = true;
  }
  
  // Проверяем элементы второго массива
  for (let j = 0; j < arr2.length; j++) {
    if (map[arr2[j]]) {
      result.push(arr2[j]);
      delete map[arr2[j]]; // предотвращаем дублирование
    }
  }
  
  return result;
}

Или с использованием Set (ES6+):

function intersectionSet(arr1, arr2) {
  const set1 = new Set(arr1);
  const result = [];
  
  for (const item of arr2) {
    if (set1.has(item)) {
      result.push(item);
      set1.delete(item); // удаляем, чтобы избежать дубликатов
    }
  }
  
  return result;
}

• Временная сложность: O(n + m) — линейная сложность
• Пространственная сложность: O(n) для хранения хэш-таблицы
• Преимущества: Хорошая производительность для массивов разного размера

3. Сортировка и два указателя

Если массивы уже отсортированы или их можно отсортировать:

function intersectionSorted(arr1, arr2) {
  arr1.sort((a, b) => a - b);
  arr2.sort((a, b) => a - b);
  
  const result = [];
  let i = 0, j = 0;
  
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      i++;
    } else if (arr1[i] > arr2[j]) {
      j++;
    } else {
      // Элементы равны — добавляем в результат
      result.push(arr1[i]);
      i++;
      j++;
      // Пропускаем дубликаты
      while (i < arr1.length && arr1[i] === arr1[i-1]) i++;
      while (j < arr2.length && arr2[j] === arr2[j-1]) j++;
    }
  }
  
  return result;
}

• Временная сложность: O(n log n + m log m) из-за сортировки
• Пространственная сложность: O(1) (если не считать память под результат)
• Преимущества: Не требует дополнительной памяти (кроме результата)

4. Сравнительный анализ

5. Особые случаи и оптимизации

1. Когда массивы уже отсортированы: сложность снижается до O(n+m) для метода двух указателей
2. При наличии дубликатов: требуется дополнительная обработка для их исключения
3. Для больших массивов: метод с хэш-таблицей предпочтительнее
4. При ограниченной памяти: метод двух указателей (если можно сортировать на месте)

6. Практические рекомендации

На практике в современных JavaScript-приложениях чаще всего используют подход с Set, так как он обеспечивает баланс между производительностью и читаемостью кода:

// Самый лаконичный и эффективный способ (ES6)
const intersection = (arr1, arr2) => {
  const set2 = new Set(arr2);
  return [...new Set(arr1.filter(item => set2.has(item)))];
};

Ключевые выводы:

• Для небольших массивов (до 100 элементов) разница в производительности незначительна
• Для больших массивов всегда предпочтительны алгоритмы с линейной сложностью O(n+m)
• Выбор алгоритма зависит от конкретных условий: отсортированы ли массивы, важна ли память, допустимы ли дубликаты
• В большинстве случаев оптимальным будет использование Set с временной сложностью O(n+m)