🤔 Если в прошлый раз мы освежили в памяти базу, то сегодня переходим к инструментам, на которых держится логика высоконагруженных систем и сложных поисковых движков

Эти методы позволяют превратить медленный перебор в изящное и быстрое решение

1️⃣ Алгоритм Дейкстры

Многие знают, что он ищет кратчайший путь. Но дьявол в деталях:

Как работает? Алгоритм использует приоритетную очередь (Min-Heap). Мы всегда выбираем «самый дешевый» следующий шаг, обновляя веса соседних вершин

Важный нюанс: Дейкстра не работает с отрицательными весами ребер (в этом случае используй алгоритм Беллмана-Форда)

Сложность O(E * log V), где E — связи, а V — узлы

2️⃣ Динамическое программирование

Два подхода: Top-down (Мемоизация) Решаем рекурсивно, сохраняя результаты в кэш

Bottom-up (Табуляция) Решаем итеративно, заполняя таблицу от малых задач к большим

3️⃣ Хеширование

Хеширование превращает данные любого размера в фиксированную строку

Коллизии возникают, когда разным данным достается один хеш. Хороший алгоритм минимизирует их, но системы должны уметь их обрабатывать (метод цепочек или открытая адресация)

😕 Плохая хеш-функция может превратить быстрый поиск O(1) в линейный список O(n)

4️⃣ Метод двух указателей и Sliding Window

Это главные инструменты для оптимизации вложенных циклов

Два указателя Обычно используются в отсортированных массивах (движемся навстречу друг другу или с разной скоростью — «заяц и черепаха»)

Скользящее окно (Sliding Window) Позволяет анализировать подмассив внутри массива, не пересчитывая его элементы заново при каждом сдвиге

😉 Снижение сложности с квадратичной O(n^2) до линейной O(n)

5️⃣ Жадные алгоритмы

Жадный алгоритм делает локально лучший выбор на каждом шагу, надеясь, что это приведет к глобальному максимуму

Где идеален? Кодирование Хаффмана (сжатие данных) и построение остовных деревьев (алгоритм Прима или Краскала)

В этом посте были ссылки, но мы их удалили по правилам Сетки