Как доказывать корректность через инварианты?
На этой странице
Инвариант - утверждение, которое остается верным во время работы алгоритма. Для новичка это простой способ объяснить, почему решение работает, а не просто "потому что код так написал".
Вопрос
Как доказывать корректность алгоритма через инварианты?
Что такое инвариант
Инвариант - это правило, которое истинно:
- до начала цикла или рекурсии;
- после каждого шага;
- в конце помогает получить ответ.
Пример:
После обработки первых 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содержит максимум по всем окнам.
Пример: binary search
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]. - Корректность - это не сложность.