Математика и алгоритмы
Страница 28 из 28.
Алгоритм Кнута-Морриса-Пратта: поиск подстроки за O(n+m)
Алгоритм Кнута-Морриса-Пратта ищет подстроку без возвратов по тексту. Разбираем префикс-функцию по шагам, оцениваем сложность и смотрим понятный пример работы.
Алгоритм Бойера-Мура: почему он ищет подстроку так быстро
Разбираем алгоритм Бойера-Мура: зачем сравнивать паттерн справа налево, как работают эвристики плохого символа и хорошего суффикса и почему поиск выходит сублинейным.
Алгоритм Дейкстры: как найти кратчайший путь в графе
Разбираем алгоритм Дейкстры на взвешенном графе по шагам: как он находит кратчайшие пути от стартовой вершины и почему ломается на ребрах с отрицательными весами.
Алгоритм Карацубы: умножение длинных чисел быстрее столбика
Разбираем алгоритм Карацубы: почему три умножения вместо четырёх ускоряют перемножение длинных чисел, как выглядит рекуррентность и зачем это нужно на практике.
Замыкания JavaScript: как функция помнит свой контекст
Замыкания JavaScript простыми словами: как лексическая область видимости позволяет функции хранить состояние между вызовами, где это применяют и какие ловушки с памятью встречаются на практике.
Якобиан полярных координат: откуда берётся r и зачем
Подробный вывод якобиана перехода к полярным координатам: объясняем, почему dx dy превращается в r dr dθ, и разбираем примеры двойных интегралов с круговой симметрией.
Алгоритм Беллмана-Форда: пути с отрицательными весами
Разбираем алгоритм Беллмана-Форда: как искать кратчайшие пути в графе с отрицательными рёбрами, ловить отрицательные циклы и чем он отличается от Дейкстры.
Цикломатическая сложность: как считать по Маккейбу
Цикломатическая сложность показывает число независимых путей в коде. Разбираем формулу Маккейба V(G)=E-N+2P, подсчёт по решающим точкам и пороги ISO для тестов.