Алгоритмическая сложность и динамическое программирование
Словарь для оценки масштабируемости любого алгоритма и три приёма ускорения медленных
Главная идея: стоимость алгоритма - это не число секунд, а функция от размера входа. O-нотация описывает, как эта стоимость растёт с ростом входа, игнорируя скорость машины и постоянные множители, чтобы можно было сравнить два алгоритма на бумаге ещё до первой строки кода. Как только вы умеете называть стоимость, вы можете с ней бороться: разделяй и властвуй, мемоизация и динамическое программирование превращают многие экспоненциальные алгоритмы в полиномиальные.
К концу вы сможете:
- читать и записывать O-оценки и объяснять, почему отбрасываются константы и младшие члены,
- ранжировать типовые классы сложности и рассуждать о компромиссе время/память,
- распознавать шаблон «разделяй и властвуй» за такими алгоритмами, как сортировка слиянием,
- превращать экспоненциальную рекурсию в линейную с помощью мемоизации, а затем в восходящее динамическое программирование.
1. Почему считают операции, а не секунды
Замер времени секундомером измеряет ваш процессор, флаги компилятора и текущее состояние кэша не меньше, чем сам алгоритм. Чтобы рассуждать об алгоритме отдельно, мы считаем число базовых операций как функцию размера входа n и спрашиваем, как это число ведёт себя при больших n.
Пусть процедура выполняет 3n + 5 сравнений. +5 - это фиксированные накладные расходы, а 3 - зависящая от машины константа на элемент. Для больших n исход решает член n. Поэтому мы говорим, что процедура имеет сложность O(n): её время растёт линейно, и удвоение входа примерно удваивает работу.
Аналогия. Когда решаете, идти пешком или ехать через всю страну, максимальная скорость машины важна меньше, чем расстояние. На достаточно долгом пути доминирует форма роста, а не постоянный множитель. O-нотация сообщает форму.