Правильный и достаточно быстрый алгоритм

Где мы на карте

Это третий блок одного проекта. Мы пользуемся данными версии 0.2, но пока описываем действия на бумаге: так можно обнаружить ошибку до написания Python.

Ситуация и вопрос

В трёх задачах одинаковые id можно заметить взглядом. Но если записей тысяча, как проверить их быстро и не пропустить повтор? Скорость важна только после того, как мы точно определили, что считать повтором и какой ответ нужен.

Новые слова без пропусков

Корректность означает, что алгоритм выполняет записанный договор для всех допустимых входов, а не только для одного примера. Контрпример — вход, на котором обещание ломается. Эффективность сравнивает нужную работу и память при росте входа. Размер входа n — здесь число задач. Линейный проход смотрит каждую запись примерно один раз. Квадратичный рост появляется при сравнении каждой записи с каждой: число пар n(n−1)/2. Множество — коллекция уникальных значений, которая обычно позволяет быстро проверить, встречалось ли id; она требует дополнительной памяти. Сложность описывает рост, а не обещает секунды на конкретном ноутбуке.

Опорный сигнал

сначала договор и контрпримеры → затем число действий и память

Разбираем шаг за шагом

Способ A: для каждой задачи сравнить её id со всеми следующими. При 4 задачах это 6 пар, при 10 — 45. Способ B: идти слева направо с пустым множеством seen; если id уже там, сообщить о повторе, иначе добавить его. Для t-01,t-02,t-03,t-02 шаги B: добавить t-01, t-02, t-03, на четвёртом обнаружить повтор. При 4 задачах проверяется не более 4 поступающих значений, но нужно место для уже встреченных id. Сравнивать следует именно id, не названия: два разных задания могут называться одинаково.

Проверка руками

Выпишите четыре id: t-01, t-02, t-03, t-02. Для попарной проверки нарисуйте пары позиций 1–2, 1–3, 1–4, 2–3, 2–4, 3–4; повтор обнаружится на пятой паре. Теперь ведите множество seen: после первых трёх шагов там три значения, на четвёртом t-02 уже есть. При подсчёте работы называйте, что именно считаете: сравнения пар или проверки принадлежности. Даже при одном и том же результате цифры 5 и 4 относятся к разным операциям; скорость на устройстве предстоит измерить позже.

Предскажите и проверьте

Что будет для пустого списка и для одного id? Повторов нет у обоих способов. А для t-01,t-01? Повтор на втором. Если id отличаются только регистром (t-01 и T-01), результат зависит от заранее записанного правила нормализации; молча менять регистр нельзя.

Поймайте ошибку

«Способ B быстрее на любом устройстве и при любом входе». Он обычно делает меньше сравнений при больших списках, но хранит множество и зависит от реализации. Выберите способ по требованиям и измерьте на реальных размерах после реализации, не выдавая учебную модель за бенчмарк.

Перенос в новую ситуацию

Для списка уже отсортированных сроков нужно найти ближайший. Подумайте, нужен ли полный просмотр, если порядок гарантирован. Сначала докажите гарантию сортировки; иначе ранний выход может дать неверный ответ.

Изменение проекта

В ALGORITHM-ru.md добавьте оба способа проверки повторных id, таблицу числа пар для n=1,4,10 и случаи t-01,t-02,t-01, пустой список и одинаковые названия с разными id. Запишите компромисс: меньше проверок ценой дополнительной памяти.

Задание и доказательство

Попросите одноклассника найти контрпример алгоритму, который сравнивает названия вместо id. Затем он должен обосновать корректность способа B: после каждого шага seen содержит ровно уже просмотренные идентификаторы. Доказательство — трасса и объяснение инварианта.

Возврат через 1, 7 и 30 дней

Завтра восстановите шесть пар для четырёх записей. Через семь дней оцените проверки для пяти записей. Через месяц сравните бумажный прогноз с измерением своей программы.

Следующий урок: Контрольная точка: алгоритмы помощника на бумаге