Конспект раздела: как разрабатывать алгоритм

Одна мысль на весь раздел

Алгоритм начинается раньше кода и кончается позже него. До кода - спецификация, размер и название задачи: они решают, какой алгоритм вообще возможен и не написан ли он уже. После кода - проверка, которая не доверяет самому алгоритму: перебор, сертификат, свойство. Между ними - сам алгоритм, и чаще всего он не придуман, а найден.

Чек-лист из десяти вопросов

ДО КОДА
 1. Что на входе: объекты, повторы, порядок, гарантии?
 2. Какой вид ответа: есть ли / сколько / все / лучший?
 3. Что значит «лучше»: критерий, равенство, нужен ли точный оптимум?
 4. Каков размер и сколько времени -> какой класс сложности допустим?
 5. Какие края: пусто, один, все равны, касание, равные времена?
ПОИСК
 6. Какой это объект: перестановка, подмножество, граф, интервалы,
    точки, строка? Есть ли у данных особая структура?
 7. К какой известной задаче сводится и чего стоят переводы?
 8. Какие признаки в формулировке и выполнено ли условие метода?
ПОСЛЕ КОДА
 9. Совпадает ли быстрое решение с перебором на всех маленьких входах?
10. Чем проверить ответ без эталона: сертификат, инвариант, отношение?

Скиена в главе «Как разрабатывать алгоритмы» советует отвечать на такие вопросы письменно и не «нет», а «нет, потому что…»: ошибка в рассуждении чаще всего прячется в отказе без причины.

Дерево решений

новая задача
├── спецификация не ясна              -> пять вопросов, ручной пример
├── размер известен
│   ├── не хватает в тысячи раз       -> другой класс алгоритма
│   ├── не хватает в разы             -> константа, замер (раздел 25)
│   └── n <= 20                       -> перебор 2ⁿ (n! - до 12)
├── объект назван
│   ├── есть в каталоге / курсе       -> сведение, условие метода
│   ├── «сколько» - ряд маленьких     -> OEIS, рекуррентность
│   ├── трудная (раздел 21)           -> раздел 22: приближение, ...
│   └── ничего не нашлось             -> перебор, убрать повторы
└── код написан
    ├── есть перебор                  -> стресс-тест, полный перебор
    ├── есть расхождение              -> уменьшить, точный признак
    ├── ответ большой, эталона нет    -> сертификат
    └── нет и сертификата             -> инварианты, метаморфные

Как главы связаны

глава	что даёт	без чего не работает следующая
как читать задачу	вход, вид ответа, критерий, бюджет, края, объект	без объекта нечего искать
как найти готовое	сведение, признаки, ряды, ускорение перебора	без перебора нечем сверять
пять разборов	путь целиком на задачах из жизни	показывает, где ломаются модели
инженерия и проверка	стресс-тест, уменьшение, сертификат, свойства	замыкает круг: спецификация проверяется

Перебор по определению проходит через все четыре главы: в первой он спецификация, во второй - стартовая точка для ускорения, в третьей - судья между моделями, в четвёртой - эталон стресс-теста.

Числа раздела

CPython: сложение 15 млн/с, dict 6 млн/с, sorted 3 млн/с
предел n при 10⁷: n log n 5·10⁵, n² 3162, n³ 215, 2ⁿ·n 19, n! 10
sorted против слияния на Python: 47 и 940 мс, n² - 1640 с
НВП, n = 200: LCS 36 400 клеток, хвосты 787 сравнений
области круга: 1, 2, 4, 8, 16, 31 - пятью членами не доказать
копии: 3160 пар -> 17; склад: 916 против 1580 км/день
расписание: граф длительностей 8:32, реально 8:42
куча: инвариант на 11-й операции, ответ неверен с 14-й
жадный размен: стресс до 10 пропустил 5 наборов из 6 с ошибкой

Объясни своими словами

Почему «найди все пары» может быть неразрешимо быстро, а «сколько пар» - нет?
Как по ограничению n ≤ 2 · 10⁵ и двум секундам понять, что квадрат не пройдёт?
Почему быстрый алгоритм надо сверять с перебором именно на краях?
Чем раскраска встреч по комнатам проще раскраски экзаменов по дням?
Что доказывает сведение к лёгкой задаче и чего оно не доказывает?
Почему пять совпавших членов ряда - ещё не формула?
Где у взвешенной медианы «перетягивание каната»?
Почему граф длительностей врёт про расписание?
Чем опасен признак «ответы разошлись» при уменьшении контрпримера?
Как проверить кратчайшие расстояния, не решая задачу заново?