Задача сводится к таким же задачам меньшего размера. Основа слиянием, быстрой сортировки, обхода деревьев и почти всей динамики.
Ключевые тезисы
- Обязательна база , иначе переполнится — самая частая ошибка.
- Мастер-теорема даёт сложность рекуррентности вида T(n) = a·T(n/b) + f(n) без раскручивания.
- Глубокая в Python упирается в лимит стека: переписывают в цикл или увеличивают лимит осознанно.
Видеолекции
Записи университетских курсов, где эта тема звучит. Где у записи есть тайм-коды, ссылка открывает её с нужной секунды; где их не проставили — с начала.
Связанные темы
Алгоритмическое мышление
Problem Pattern Recognition85%
Как распознать паттерн задачи · Алгоритмы и структуры данныхУровень над алгоритмами: по формулировке условия понять, какой приём здесь работает. «Отсортированный массив», «подряд идущие элементы», «ближайший больший справа» — каждая такая фраза указывает на конкретное семейство решений.
Time and Space Complexity85%
Асимптотическая сложность · Алгоритмы и структуры данныхСпособ сравнить алгоритмы, не запуская их: как растёт время работы с ростом входа. Отбрасывает константы и оставляет то, что решает на больших данных.
Dynamic Programming85%
Динамическое программирование · Алгоритмы и структуры данныхПеребор, в котором каждое подсостояние считается ровно один раз. Превращает экспоненциальный перебор в полиномиальный, если подзадачи перекрываются.
Greedy Algorithms85%
Жадные алгоритмы · Алгоритмы и структуры данныхНа каждом шаге берём локально лучший вариант и не пересматриваем решение. Работает не всегда — но когда работает, проще и быстрее динамики.
Binary Search85%
Бинарный поиск · Алгоритмы и структуры данныхПоловинное деление на отсортированных данных: за логарифм шагов вместо линейного перебора. Приём шире поиска — им ищут ответ в любой монотонной задаче.
Тема встречается в тесте по направлениям — ошибки приведут обратно на эту страницу.
Глава «Алгоритмы и структуры данных» последний раз правилась . Нашли ошибку — напишите.