рекурсия

SRT Алгоритм Сортировка слиянием Делит пополам, сортирует половины и сливает: n log n на любом входе, устойчиво, годится для внешней памяти. O(n log n) 2 задачи DS Структура данных Дерево отрезков Минимум, максимум и сумма на любом отрезке с изменениями на ходу: оба действия за O(log n). O(log n) на запрос и на изменение 2 задачи GRA Алгоритм Поиск в глубину Идёт вглубь, отмечает вход и выход каждой вершины и по ним находит циклы за O(V + E). O(V + E) 2 задачи DP Приём Динамическое программирование Сводим задачу к подзадачам, решаем каждую один раз и храним ответы в таблице. состояния × переходы 2 задачи DP Приём Динамика на деревьях Ответ поддерева — из ответов детей: проход от листьев к корню, а для всех корней сразу — перерасчёт с корня. O(n) 2 задачи PAR Приём Перебор с возвратом Строить решение по шагу, сразу проверять и отступать из тупика: судоку, ферзи, раскраски. O(bᵈ) в худшем случае 2 задачи PAR Приём Разделяй и властвуй Разрезать, решить части так же, склеить; сколько это стоит — по уровням дерева рекурсии и основной теореме. T(n) = a·T(n/b) + f(n) 2 задачи NUM Алгоритм Алгоритм Евклида Наибольший общий делитель двух чисел за O(log n) делений с остатком. O(log min(a, b)) 2 задачи NUM Алгоритм Умножение Карацубы Три умножения половин вместо четырёх: n^1,585 вместо n² — в CPython, Go и GMP. O(n^1,585) 2 задачи NUM Алгоритм Быстрое преобразование Фурье Дискретное преобразование Фурье за O(N log N): спектры, свёртки, умножение многочленов и больших чисел. O(N log N) 2 задачи NUM~ Алгоритм Численное интегрирование Площадь под кривой суммой: трапеции, Симпсон, узлы Гаусса, адаптивный шаг и оценка ошибки по Рунге. O(n) вычислений функции 2 задачи ML Алгоритм Решающее дерево Отвечает цепочкой вопросов «признак ≤ порог?»; каждый вопрос выбран так, чтобы неопределённость упала сильнее всего. O(h · F · n log n) построение; O(h) ответ 2 задачи TEC Приём Мемоизация Запомнить ответ функции для каждого набора аргументов, чтобы не считать его заново: экспонента превращается в многочлен. O(число разных аргументов × работа на один вызов) 2 задачи TEC Приём Профилировщики Не гадать, где программа тратит время, а посмотреть: выборочный профилировщик, cProfile и pprof, граф пламени. доля функции ± √(p(1−p)/N) 1 задача