re:re:actable
Урок 054 минуты чтения

Как доказывать корректность через инварианты?

На этой странице
Кратко

Инвариант - утверждение, которое остается верным во время работы алгоритма. Для новичка это простой способ объяснить, почему решение работает, а не просто "потому что код так написал".

Вопрос

Как доказывать корректность алгоритма через инварианты?

Что такое инвариант

Инвариант - это правило, которое истинно:

  1. до начала цикла или рекурсии;
  2. после каждого шага;
  3. в конце помогает получить ответ.

Пример:

После обработки первых i элементов Set содержит ровно те элементы,
которые уже встречались раньше.

Это инвариант для многих задач с Set.

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

function hasDuplicate(nums: number[]): boolean {
  const seen = new Set<number>()
 
  for (const num of nums) {
    if (seen.has(num)) return true
    seen.add(num)
  }
 
  return false
}

Инвариант:

Перед каждой итерацией seen содержит все числа, которые стоят левее текущего элемента.

Почему корректно:

  • если num уже есть в seen, значит он встречался раньше, дубликат найден;
  • если num не было, мы добавляем его, и инвариант сохраняется;
  • если цикл закончился, ни один элемент не встретился повторно.

Пример: sliding window

function maxSumFixed(nums: number[], k: number): number {
  let sum = 0
 
  for (let i = 0; i < k; i++) {
    sum += nums[i]
  }
 
  let best = sum
 
  for (let right = k; right < nums.length; right++) {
    sum += nums[right]
    sum -= nums[right - k]
    best = Math.max(best, sum)
  }
 
  return best
}

Инвариант:

После каждого шага sum равен сумме текущего окна длины k,
а best равен максимальной сумме среди всех окон, которые уже были рассмотрены.

Почему корректно:

  • начальное окно посчитано правильно;
  • на каждом шаге добавляем новый элемент и удаляем старый;
  • размер окна остается k;
  • best обновляется после каждого нового окна;
  • после последнего окна best содержит максимум по всем окнам.
function binarySearch(nums: number[], target: number): number {
  let left = 0
  let right = nums.length - 1
 
  while (left <= right) {
    const mid = Math.floor((left + right) / 2)
 
    if (nums[mid] === target) return mid
    if (nums[mid] < target) left = mid + 1
    else right = mid - 1
  }
 
  return -1
}

Инвариант:

Если target существует, он находится внутри диапазона [left, right].

Почему корректно:

  • сначала весь массив является диапазоном поиска;
  • если nums[mid] < target, то target не может быть слева от mid, потому что массив отсортирован;
  • если nums[mid] > target, то target не может быть справа от mid;
  • мы не удаляем из поиска часть, где target мог бы находиться;
  • если диапазон стал пустым, target отсутствует.

Пример: BFS

Инвариант BFS:

Queue содержит вершины текущего или следующего слоя,
а вершина впервые посещается на минимальном расстоянии от start.

Поэтому BFS дает shortest path в unweighted graph.

Как формулировать инвариант

Хороший инвариант отвечает на вопрос:

Что точно верно после обработки части input?

Шаблоны:

После обработки первых i элементов ...
Перед каждой итерацией ...
В окне [left, right] ...
В stack лежат ...
В dp[i] хранится ...
В visited находятся ...

Инвариант для DP

Для DP почти всегда нужно сказать:

dp[i] означает ...

Пример:

dp[i] - количество способов подняться на i-ю ступеньку.

Transition:

dp[i] = dp[i - 1] + dp[i - 2]

Почему:

На i-ю ступеньку можно попасть либо с i - 1 одним шагом,
либо с i - 2 двумя шагами.

Что важно помнить: частые ошибки

  • Говорить "оно работает", но не объяснять почему.
  • Формулировать инвариант слишком общо.
  • Не объяснять, почему шаг сохраняет инвариант.
  • Не связывать инвариант с финальным ответом.
  • Путать инвариант и сложность.
  • Доказывать код, а не идею алгоритма.

Что отвечать на собеседовании?

Я объясняю корректность через инвариант: что верно до цикла, что сохраняется после каждого шага и почему в конце из этого следует ответ. Например, для Set инвариант: после обработки первых i элементов он содержит все уже встреченные значения. Для binary search: если target существует, он всегда остается внутри [left, right].

Мини-шпаргалка

  • Инвариант = что остается истинным.
  • Для цикла: до, после шага, в конце.
  • Для Map/Set: что уже обработано.
  • Для window: что находится в окне.
  • Для stack: что лежит в стеке.
  • Для DP: что означает dp[i].
  • Корректность - это не сложность.

Документация

Wikipedia: Loop invariant.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам