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

Временная сложность вложенных циклов

Это базовый, но важный вопрос об анализе алгоритмов. Разберусь детально с примерами.

Основной случай: O(n²)

Два вложенных цикла с одинаковым диапазоном имеют временную сложность O(n²) (квадратичная).

function fullTraverse(arr) {
  let count = 0;
  
  // Внешний цикл: n итераций
  for (let i = 0; i < arr.length; i++) {
    // Внутренний цикл: n итераций для каждой итерации внешнего
    for (let j = 0; j < arr.length; j++) {
      count++; // Это выполнится n × n раз
    }
  }
  
  return count; // Вернет n²
}

const arr = [1, 2, 3, 4, 5]; // n = 5
console.log(fullTraverse(arr)); // 25 (5 × 5 = 25)

Почему O(n²)?

Это произведение количества итераций:

• Внешний цикл: выполняется n раз
• Внутренний цикл: выполняется n раз для каждой итерации внешнего
• Итого: n × n = n²

Визуализация:

Внешний цикл:  i = 0, 1, 2, 3, 4        (5 раз)
Для каждого i:
  Внутренний:  j = 0, 1, 2, 3, 4        (5 раз)

Всего операций: 5 × 5 = 25 = O(5²)

Реальные примеры

Пример 1: Поиск дубликатов

// O(n²) — для каждого элемента ищем совпадение
function findDuplicates(arr) {
  const duplicates = [];
  
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) {
        duplicates.push(arr[i]);
      }
    }
  }
  
  return duplicates;
}

findDuplicates([1, 2, 3, 2, 4, 3]); // O(n²)

Пример 2: Сортировка пузырьком

// 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]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  
  return arr;
}

bubbleSort([5, 3, 1, 4, 2]); // O(n²)

Пример 3: Создание матрицы

// O(n²) — создание двумерного массива n×n
function createMatrix(size) {
  const matrix = [];
  
  for (let i = 0; i < size; i++) {
    const row = [];
    for (let j = 0; j < size; j++) {
      row.push(i * size + j);
    }
    matrix.push(row);
  }
  
  return matrix;
}

const matrix = createMatrix(4);
// Всего итераций: 4 × 4 = 16

Варианты сложности с вложенными циклами

1. Разные размеры циклов: O(n × m)

// Если циклы итерируют по разным размерам
function traverse(arr1, arr2) {
  let count = 0;
  
  for (let i = 0; i < arr1.length; i++) {      // n итераций
    for (let j = 0; j < arr2.length; j++) {    // m итераций
      count++;
    }
  }
  
  return count; // n × m
}

traverse([1,2,3], [1,2,3,4,5]); // 3 × 5 = 15 = O(n × m)

2. Ограниченный внутренний цикл: O(n)

// Внутренний цикл выполняется фиксированное количество раз
function limitedInner(arr) {
  let count = 0;
  
  for (let i = 0; i < arr.length; i++) {       // n итераций
    for (let j = 0; j < 5; j++) {               // всегда 5 итераций
      count++;
    }
  }
  
  return count; // n × 5 = O(n)
}

limitedInner([1,2,3,4,5,6]); // 6 × 5 = 30 = O(6) = O(n)

3. Уменьшающийся цикл: O(n²)

// Сложение от 1 до n + от 1 до n-1 + ... + 1
// 1 + 2 + 3 + ... + n = n(n+1)/2 ≈ O(n²)
function decreasingInner(arr) {
  let count = 0;
  
  for (let i = 0; i < arr.length; i++) {
    for (let j = i; j < arr.length; j++) {     // цикл уменьшается
      count++;
    }
  }
  
  return count;
}

// Для n=5:
// i=0: 5 итераций
// i=1: 4 итерации
// i=2: 3 итерации
// i=3: 2 итерации
// i=4: 1 итерация
// Итого: 5+4+3+2+1 = 15 = 5(5+1)/2 = O(n²)

decreasingInner([1,2,3,4,5]); // 15 операций

Три вложенных цикла: O(n³)

function tripleNested(arr) {
  let count = 0;
  
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      for (let k = 0; k < arr.length; k++) {
        count++; // n × n × n
      }
    }
  }
  
  return count; // n³
}

tripleNested([1,2,3]); // 3 × 3 × 3 = 27 = O(3³)

График роста O(n²)

Операции
  25 |              ●
  20 |              │
  15 |          ●   │
  10 |      ●   │   │
   5 |  ●   │   │   │
   0 |──●───●───●───●───
      1  2  3  4  5  n

n = 1: O(1) = 1
n = 2: O(4) = 4
n = 3: O(9) = 9
n = 4: O(16) = 16
n = 5: O(25) = 25

Практические последствия O(n²)

Вывод: O(n²) приемлема только для малых n (до ~10,000). Для больших данных нужны оптимизированные алгоритмы (O(n log n), O(n)).

Оптимизация: от O(n²) к O(n)

Плохо: O(n²) поиск дубликатов

function findDuplicatesSlow(arr) {
  const duplicates = [];
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) {
        duplicates.push(arr[i]);
      }
    }
  }
  return duplicates;
}

Хорошо: O(n) с использованием Set

function findDuplicatesFast(arr) {
  const seen = new Set();
  const duplicates = [];
  
  for (const num of arr) {
    if (seen.has(num)) {
      duplicates.push(num);
    }
    seen.add(num);
  }
  
  return duplicates; // O(n)
}

Best Practices

1. Избегай вложенных циклов, если возможно
2. Используй структуры данных — Set, Map, Hash для O(1) поиска
3. Выноси вычисления из внутренних циклов
4. Используй встроенные методы — они оптимизированы

// ❌ Плохо: O(n²)
const arr1 = [1, 2, 3];
const arr2 = [2, 3, 4];
const common = [];
for (const x of arr1) {
  for (const y of arr2) {
    if (x === y) common.push(x);
  }
}

// ✅ Хорошо: O(n)
const set2 = new Set(arr2);
const common = arr1.filter(x => set2.has(x)); // O(n)

Заключение

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