Алгоритмы с нуля
Правильный ли алгоритм?
Ты проверяешь функцию на [3, 9, 2, 7] и она возвращает 9 — правильно. Проверяешь на [1, 2, 3] и возвращает 3 — правильно. Чувствуешь уверенность. А затем на производстве она падает на пустом списке. Или возвращает неправильный ответ для всех отрицательных чисел. Проверка нескольких примеров — это не то же самое, что уверенность в том, что алгоритм правилен для каждого возможного входа.
После этого урока ты можешь определить, что значит корректность алгоритма, заметить ошибки, рассматривая граничные случаи, и использовать инвариант цикла, чтобы доказать, что цикл решает задачу правильно.
Алгоритм корректен, если он выдаёт правильный результат для каждого действительного входа, не только для тех, что ты проверил. Это определение требует двух вещей:
- Спецификацию — точное утверждение о том, какой результат ожидается для какого входа. Например: «Дан список чисел, верни наибольшее.»
- Доказательство — логический аргумент, что алгоритм соответствует спецификации для всех возможных входов.
Тестирование — это не доказательство. Тестирование может обнаружить ошибки, но не может доказать корректность, потому что ты не можешь проверить каждый возможный вход. Граничные случаи — необычные или пограничные входы вроде пустых списков, одного элемента или всех равных значений — вот где скрываются ошибки.
Инструмент для доказательства того, что цикл правилен, называется инвариант цикла: утверждение о цикле, которое верно до его запуска, остаётся верным после каждой итерации и полезно, когда цикл завершается.
Рассмотри функцию largestOf из урока 01:
1
function largestOf(numbers) {
2
let largest = numbers[0];
3
for (let i = 1; i < numbers.length; i++) {
4
if (numbers[i] > largest) {
5
largest = numbers[i];
6
}
7
}
8
return largest;
9
}
- L2 После этой строки largest = numbers[0]
- L3 Цикл: мы обновим largest, когда увидим больше чисел
- L8 Инвариант: после обработки numbers[0..i], largest хранит максимум
Инвариант цикла такой: «После обработки первых i+1 чисел (с индекса 0 по индекс i), largest содержит наибольшее из этих чисел.»
- До цикла: Мы устанавливаем
largest = numbers[0], поэтому инвариант верен для i=0. - Каждая итерация: Мы сравниваем
numbers[i]сlargest. Если оно больше, мы обновляемlargest. В любом случае, после итерацииlargestостаётся наибольшим из чисел, которые мы видели до сих пор. - После цикла: Цикл выходит, когда
i = numbers.length. По инварианту,largest— наибольшее из всех чисел. Это то, что мы обещали вернуть.
Этот логический аргумент доказывает, что алгоритм правилен — не тестированием, а рассуждением.
Напишем функцию largestOf и затем докажем её корректность:
function largestOf(numbers) {
let largest = numbers[0];
for (let i = 1; i < numbers.length; i++) {
if (numbers[i] > largest) {
largest = numbers[i];
}
}
return largest;
}Попробуй её на нескольких входах:
Все эти примеры проходят. Но ты можешь попасть в ловушку: думать, что раз я это проверил, то оно правильно. Это заблуждение. Инвариант цикла — вот что даёт тебе уверенность.
Проследим алгоритм на [-5, -1, -10], чтобы увидеть инвариант цикла в действии:
1
function largestOf(numbers) {
2
let largest = numbers[0];
3
for (let i = 1; i < numbers.length; i++) {
4
if (numbers[i] > largest) {
5
largest = numbers[i];
6
}
7
}
8
return largest;
9
}
Инвариант остаётся верным на каждом шаге. Это даёт нам уверенность не только для этого примера, но для каждого действительного входа.
Доказательство корректности не имеет прямой стоимости в терминах шагов — это логический аргумент, не вычисление. Но понимание структуры алгоритма (инвариант цикла) часто делает код быстрее или яснее. Пока что ключевая идея: правильный алгоритм — это алгоритм, о котором ты можешь рассуждать с инвариантом.
Что такое инвариант цикла?
Почему только тестирование недостаточно для доказательства корректности алгоритма?
Если цикл обрабатывает элементы с индекса 0 по n-1, и инвариант — «largest содержит максимум элементов [0..i]», каким будет инвариант, когда цикл заканчивается и i = n?
Алгоритм падает на отрицательных числах, хотя работает на положительных. Это пример чего?
Расставь шаги для доказательства корректности цикла с использованием инварианта цикла:
- Докажи, что инвариант верен до цикла (инициализация)
- Докажи, что инвариант остаётся верным после каждой итерации (поддержание)
- Покажи, что когда цикл выходит, инвариант говорит нам, что ответ правильный (завершение)
- Сформулируй, что такое инвариант цикла
Граничные случаи
Граничный случай: пустой список. Функция падает на пустом списке, потому что numbers[0] не существует. Правильная версия сначала проверила бы if (numbers.length === 0). Спецификация должна сказать, что вернуть для пустого входа — может быть, null или выкинуть ошибку. Без такой спецификации ты не можешь сказать, правильна ли функция.
Частая ошибка
Багги вариант. Что если мы инициализируем largest = 0 вместо largest = numbers[0]?
function largestOf_WRONG(numbers) {
let largest = 0; // БАГ: должно быть numbers[0]
for (let i = 0; i < numbers.length; i++) {
if (numbers[i] > largest) {
largest = numbers[i];
}
}
return largest;
}Проверка: largestOf_WRONG([-5, -3, -1]) возвращает 0, а не -1. Это падает на всех отрицательных списках. Инвариант цикла перехватил бы это: если мы инициализируем largest = 0, инвариант «largest содержит максимум [0..i]» ложен ещё до начала цикла, потому что максимум [-5] — это -5, не 0. Ложный инвариант означает ложный алгоритм.
Друг проверяет алгоритм на 100 случайных входах и он проходит все. Доказывает ли это, что алгоритм правильный?
Алгоритм корректен, если он выдаёт правильный результат для каждого действительного входа. Это определяется спецификацией — что должен выдать каждый вход. Тестирование может обнаружить ошибки, но не может доказать корректность, потому что ты не можешь проверить каждый вход. Граничные случаи — необычные или пограничные входы — вот где скрываются ошибки.
Инвариант цикла — это утверждение о цикле, которое верно до его запуска, остаётся верным после каждой итерации и помогает доказать, что цикл правилен. Доказав три вещи (инициализацию, поддержание, завершение), ты можешь быть уверен, что цикл работает для всех входов. Это логическое доказательство, не просто уверенность от тестирования.