Приведи пример квадратичной сложности алгоритма

Разбор алгоритма с квадратичной сложностью O(n²)

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

Классический пример: алгоритм сортировки пузырьком

Рассмотрим алгоритм пузырьковой сортировки — канонический пример квадратичной сложности:

function bubbleSort(arr) {
  const n = arr.length;
  
  // Внешний цикл: проход по всем элементам
  for (let i = 0; i < n; i++) {
    // Внутренний цикл: сравнение соседних элементов
    for (let j = 0; j < n - i - 1; j++) {
      // Сравнение и обмен местами при необходимости
      if (arr[j] > arr[j + 1]) {
        // Обмен значениями
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  
  return arr;
}

// Пример использования
const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
console.log('Отсортированный массив:', bubbleSort(unsortedArray));

Анализ сложности пузырьковой сортировки

Математическое обоснование:

• В худшем случае (массив отсортирован в обратном порядке) выполняется примерно n*(n-1)/2 сравнений
• Первый элемент требует (n-1) сравнений
• Второй элемент требует (n-2) сравнений
• И так далее: Σ = (n-1) + (n-2) + ... + 1 = n*(n-1)/2
• При больших n это приближается к n²/2, что является O(n²)

Как распознать квадратичную сложность на практике

Типичные признаки:

1. Вложенные циклы, где оба зависят от размера входных данных
2. Обработка матриц или таблиц, где необходимо обойти все строки и столбцы
3. Попарные сравнения всех элементов множества

Другие примеры алгоритмов O(n²)

1. Сравнение всех пар элементов в массиве

function findAllPairs(array) {
  const pairs = [];
  
  for (let i = 0; i < array.length; i++) {
    for (let j = i + 1; j < array.length; j++) {
      // Обработка каждой уникальной пары
      pairs.push([array[i], array[j]]);
    }
  }
  
  return pairs;
}

2. Простая реализация поиска пересечения множеств

function findIntersection(array1, array2) {
  const intersection = [];
  
  for (let i = 0; i < array1.length; i++) {
    for (let j = 0; j < array2.length; j++) {
      if (array1[i] === array2[j]) {
        intersection.push(array1[i]);
        break;
      }
    }
  }
  
  return intersection;
}

3. Генерация таблицы умножения

function generateMultiplicationTable(n) {
  const table = [];
  
  for (let i = 1; i <= n; i++) {
    const row = [];
    for (let j = 1; j <= n; j++) {
      row.push(i * j);
    }
    table.push(row);
  }
  
  return table;
}

Практические последствия квадратичной сложности

Производительность на разных объемах данных:

• При n = 10: ~100 операций
• При n = 100: ~10,000 операций
• При n = 1000: ~1,000,000 операций
• При n = 10000: ~100,000,000 операций

Оптимизация квадратичных алгоритмов

Стратегии улучшения:

1. Использование более эффективных алгоритмов:

   • Замена пузырьковой сортировки на быструю сортировку O(n log n)
   • Использование хэш-таблиц для исключения вложенных циклов

2. Пример оптимизации с O(n²) на O(n):

// Квадратичная версия O(n²)
function hasDuplicateQuadratic(array) {
  for (let i = 0; i < array.length; i++) {
    for (let j = i + 1; j < array.length; j++) {
      if (array[i] === array[j]) return true;
    }
  }
  return false;
}

// Оптимизированная линейно-логарифмическая версия O(n log n)
function hasDuplicateOptimized(array) {
  const sorted = [...array].sort(); // O(n log n)
  for (let i = 1; i < sorted.length; i++) { // O(n)
    if (sorted[i] === sorted[i - 1]) return true;
  }
  return false;
}

// Оптимизированная линейная версия O(n) с использованием Set
function hasDuplicateOptimal(array) {
  const seen = new Set(); // Хэш-таблица
  for (const item of array) {
    if (seen.has(item)) return true;
    seen.add(item);
  }
  return false;
}

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

Ситуации, где O(n²) может быть оправдано:

1. Малые наборы данных (n < 1000)
2. Простые одноразовые операции
3. Прототипирование и начальная разработка
4. Задачи, где важнее простота реализации, чем производительность

Заключение: Квадратичные алгоритмы — важная концепция, понимание которой помогает распознавать узкие места в производительности. Хотя они редко используются в production-коде для больших данных, их изучение помогает развивать интуицию о сложности алгоритмов и понимать, когда необходима оптимизация. В современном frontend-разработке особенно важно избегать квадратичных операций при работе с большими массивами данных в интерфейсах, чтобы не блокировать основной поток и обеспечивать плавный пользовательский опыт.