Читаем ограничения

Давайте посмотрим, как ограничения меняют алгоритм, который ты бы написал.

Сценарий 1: n ≤ 10

Задача: «Найди максимальную сумму любого подмножества массива».

Ограничение: n ≤ 10.

Подход: Перебор. Попробуй все 2^n подмножеств. Это 2^10 = 1024 операции. Мгновенно.

function maxSubsetSum(arr) {
  let max = 0;
  // Пройди все 2^n подмножеств, используя битовую маску
  for (let mask = 0; mask < (1 << arr.length); mask++) {
    let sum = 0;
    for (let i = 0; i < arr.length; i++) {
      if (mask & (1 << i)) sum += arr[i];
    }
    max = Math.max(max, sum);
  }
  return max;  // O(2^n)
}

При n ≤ 10 это решение O(2^n) хорошо. Ты не пытаешься быть умным. Ограничение даёт тебе разрешение на перебор.

Сценарий 2: n ≤ 1 000

Задача: «Найди самую длинную общую подпоследовательность (LCS) двух строк».

Ограничение: n ≤ 1 000 (длина каждой строки).

Подход: Динамическое программирование. Построй таблицу 2D размером n × n. Это 10⁶ операций (заполнение таблицы). Возможно.

function lcs(s1, s2) {
  const n = s1.length, m = s2.length;
  const dp = Array(n + 1).fill(0).map(() => Array(m + 1).fill(0));
  
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[n][m];  // O(n²)
}

При n ≤ 1 000 O(n²) безопасна. Если бы n было 10⁶, это не сработало бы.

Сценарий 3: n ≤ 10⁶

Задача: «Посчитай, сколько элементов в массиве больше среднего значения».

Ограничение: n ≤ 10⁶.

Подход: Один проход. Вычисли сумму (O(n)), вычисли среднее, посчитай (O(n)). Итого: O(n). ~10⁶ операций. Мгновенно.

function countAboveAverage(arr) {
  const sum = arr.reduce((a, b) => a + b, 0);
  const avg = sum / arr.length;
  return arr.filter(x => x > avg).length;  // O(n)
}

При n ≤ 10⁶ требуется один проход. O(n²) это 10¹² операций — невозможно. O(n log n) это ~2×10⁷ операций — излишне для этой задачи (хотя всё ещё приемлемо). O(n) идеален.

Эти три сценария показывают один принцип: ограничение сужает, какая сложность вообще стоит рассматривать.

Давайте проследим, как ограничение исключает варианты. Представь, что ты читаешь задачу:

Условие задачи: «Дан массив размером n, найди, существует ли пара элементов, чья сумма равна target».

Теперь ты читаешь ограничение: «1 ≤ n ≤ 100 000».

      1
      Ограничение: n ≤ 100 000
    

      2
      Бюджет: ~10^8 операций
    

      3
      Работай в обратном направлении, чтобы найти нужную сложность...
    

Ограничение не говорит тебе, какой O(n log n) алгоритм использовать, но оно говорит, что всё медленнее не сработает. Это бесценно.