bkoshelev/grokking-algorithms-book

Конспект, алгоритмы и задания из книги "Грокаем алгоритмы"

Структуры данных изучены:

• массивы

• связанные списки

• стек вызовов (LIFO)

• хэш-таблица

• графы

• очередь (FIFO)

• множества

Алгоритмы поиска:

• простой поиск (перебор)

• бинарный поиск (разделяй и властвуй) (больше/меньше от середины)

• поиск в ширину (для невзвешенных графов) (по уровням вширь) (поиск кратчайшего пути по количеству сегментов)

• Алгоритм Дийкстры (для направленных ациклических взвешенных графов c ненулевыми весами)

Алгоритмы сортировки:

• сортировка выбором (нашли - бросили в новую кучу)

• быстрая сортировка (разделяй и властвуй) (больше/меньше от середины)

Паттерны:

• разделяй и властвуй (упрощение до базового случая)

• жадный алгоритм (выбирая на каждом шаге локально-оптимальное решение,

в итоге получаем глобально-оптиимальное)

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

• динамическое программирование — метод решения сложных задач, разбиваемых на подзадачи, которые решаются в первую очередь.