Как оценить число состояний и переходов в ДП, чтобы заранее понять, пройдёт ли по времени?

Question

Часто придумываю ДП, кодирую — и ловлю TLE, потому что не прикинул заранее асимптотику. Как до написания кода аккуратно оценить сложность ДП по числу состояний и стоимости перехода, и с каким бюджетом операций сравнивать на CF (1–2 сек)?

Кристина Киселёва · Accepted Answer

Базовая формула: время ДП = (число состояний) × (стоимость одного перехода). 1. Число состояний — произведение размеров всех измерений таблицы. Примеры: - 1D рюкзак: состояний $O(n\cdot W)$. - interval DP dpij: $O(n^2)$ состояний. - bitmask DP dpmaski: $O(2^n \cdot n)$. - digit DP dpposremtight: $O(	ext{len}\cdot k\cdot 2)$. 2. Стоимость перехода — сколько работы на вычисление одного состояния: - перебор точки разбиения в interval DP: $O(n)$ → итого $O(n^3)$. - перебор соседа в TSP: $O(n)$ → итого $O(2^n n^2)$. - константа (Фибоначчи): $O(1)$ → итого = числу состояний. Бюджет операций на Cod…

Игорь Михайлов · Answer

Что ещё учитывать помимо голой формулы:

Память считается отдельно: число состояний × размер ячейки. $2^{20}$ long long = 8 МБ — ок, $2^{24}$ — уже 128 МБ, MLE. Часто память — более жёсткий лимит, чем время.
Константа реализации. unordered_map-мемоизация в 10–50× медленнее массива. Рекурсия добавляет накладные. Битовые операции и кэш-дружелюбный обход (по строкам) ускоряют в разы.
Сублинейные переходы. Иногда перебор в переходе ускоряется префиксными суммами / деревом отрезков / CHT / монотонной очередью — это снижает $O(\text{переход})$ и весь ДП. Перед кодом полезно прикинуть: «а нельзя ли переход сделать за $O(1)$ / $O(\log)$ вместо $O(n)$ ?»

Правило большого пальца: ограничения в условии (n ≤ ...) намекают на целевую сложность. $n\le 20$ → ждут $2^n$ ; $n\le 500$ → $O(n^3)$ ; $n\le 5000$ → $O(n^2)$ ; $n\le 10^5$ → $O(n\log n)$ .

Как оценить число состояний и переходов в ДП, чтобы заранее понять, пройдёт ли по времени?

2 ответа

Ваш ответ