Этапы динамического программирования

1. Проблему делять на меньшую перекрывающую подзадачу

2. Оптимальное решение достигается при помощи использования оптимального решения небольших задач

3. Под капотом, всегда (почти всегда) используется memoization

Data Science: Алгоритмы и Структуры данных

Мемоизация (Memoization)

По факту - это всего лишь сохранение результатов выполнения функций, чтобы предотвратить повторные вычисления с теми же самыми параметрами.

Это один из способов оптимизаци, который применяется для увелечения скорости выполнения программ или подпрограмм.

Алгоритм работы:

1. Если функция не вызывалась, то вызвать ее и сохранить результат

2. Если вызывалась, достать сохраненный результат по ключу (к примеру по параметрам)

Как видно, мемоизацию можно организовать при помощи кэша(ключ-значение). В дальнейшем мы об этом более подробно поговорим!

Data Science: Алгоритмы и Структуры данных

Быстрая сортировка (Quick Sort)

Быстрая сортировка - является высокоэффективным алгоритмом сортировки. Основана она на разбиении массива на меньше подмассивы. Большой массив делится на 2 более маленьких: один из них содержит значение меньше выбранного (pivot), другой больше значения pivot.

Базовая суть алгоритма представлена в GiF. Посмотрите ее внимательно!

Data Science: Алгоритмы и Структуры данных

Основа алгоритма Quick Sort

Как я уже говорил сегодня, суть алгоритма заключается в разделении массива на два подмассива.

Этот алгоритм эффективен для больших объемов данных, так как худшая сложность составит О(n^2)

Алгоритм

1. Выберите наибольшее значение индекса - в качестве pivot

2. Возьмите 2 переменные, чтобы указать левую и правую часть списка. Исключая наш pivot. Эта переменная и будет хранить наш массив слева и справа

3. Переупорядочьте массив, помещая элемент на его окончательно место

4. Отсортируйте рекурсивно элементы слева от разрешающего

5. Аналогично отсортируйте и правую сторону

Data Science: Алгоритмы и Структуры данных

Найти наименьший/наибольший элемент в несортированном массиве

Дан массив и число k, где k меньше размера массива, нам нужно найти k-й наименьший элемент в данном массиве. При этом задано, что все элементы массива различны.

Data Science: Алгоритмы и Структуры данных

Решение проблемы в поиске наименьшего/наибольшего элемента

Алгоритм 1

Простое решение - отсортировать данный массив с помощью сортировки О(N log N). После чего вернуть элемент с индексом K-1 в отсортированном массиве

Алгоритм 2

Можно оптимизировать - создав минимальную кучу из заданных n элементов и вызвать стандартный метод extractMin (что такое Heap(куча) - мы как раз поговорим завтра)

Data Science: Алгоритмы и Структуры данных

Heap (куча) - структура данных

Куча - это особая древовидная структура данных, в которой дерево представляет собой законченное двоичное дерево. Обычно кучи бывают 2х типов:

1. Max-Heap - ключ, в корневом узле, должен быть наибольшим среди ключей, присутсвующих во всех дочерних элементах. Это свойство рекурсивно истинно для всех последующих от корня узла

2. Min-Heap - полностью наоборот. То есть в корне находится самый минимальный элемент.

Data Science: Алгоритмы и Структуры данных

Представление Двоичной кучи

Как мы вчера уже поняли - двоичная куча - это полноценное двоичное дерево. Представляется куча в виде массива.

Корневой элемент будет всегда в arr0 (нулевом индексе массива). В табличке (на картинке) - как раз указано, как в дальнейшем берутся индексы.

Есть интересные свойства:

1. arr(i-1) / 2 - вернет всегда родительский узел

2. arr(2 * i) + 1 - вернет левый дочерний узел

3. arr(2 * i) + 2 - вернет правый дочерний узел

Data Science: Алгоритмы и Структуры данных

Операции над Min Heap

1. getMin - возвращает корневой элемент вашего Min Heap

2. extractMin - удаляет минимальный элемент из MinHeap (сложность О(logN) из-за того что надо поддерживать свойства кучи)

3. reduceKey - уменьшает значение ключа (так же сложность O(logN)

4. insert - вставка нового элемента (занимает также O(logN)) Добавит вам новый ключ в конец дерева, если новый ключ больше, чем родительский, вам не придется ничего делать. В противном случае нужно пройти вверх, чтобы исправить свойства кучи

5. delete - удаление ключа (также займет в худшем случае O(logN)

Data Science: Алгоритмы и Структуры данных

Биномиальная куча

Основным применением двоичной кучи является реализация очереди приоритетов. Биномиальная куча - это расширение обычной двоичной кучи, которое обеспечивет более быструю операцию объеденения или слияния.

Биномиальное дерево порядка 0 имеет 1 узел. Кго уровня можно построить, взяв два биномиальных дерева порядка к-1 и сделав одно из них крайним левым дочерним элементом.

Data Science: Алгоритмы и Структуры данных

Свойства биномиального дерева

1. У данного дерева 2К узлов
2. Глубина дерева равна К
3. На глубине i имеется ровно kCi узлов для i = 0, 1, ..., k
4. Корень дерева имеет степень k, а потомки корня сами являются биномиальными деревьями с порядком k-1, k-2,..0 слева направо

Data Science: Алгоритмы и Структуры данных

Операции над биномиальной кучей

1. insert(H, k) - вставкляет ключ К в биномиальную кучу H. Эта операция сначала создает биномиальную кучу с одним ключом, а затем вызывает объеденение для H

2. getMin(H) - пройдется по списку корней биномиальных деревьев и выдаст вам минимальный ключ

3. extractMin(H) - сначала вызывается метод getMin(), чтобы найти минимальное ключевое значение, после чего создаст новое биномиальное дерево, правильно его отформатировав

4. delete(H) - операция удаления, как и с операцией удаления в бинарном дереве: сначала уменьшает ключ до минус бесконечности, а после вызывает extractMin()

5. reduceKey(H) - сравниваем ключ уменьшения с ключом родительским, и если родительский ключ больше , мы меняем ключи и повторяем для родительского узла. Останавливаемся тогда, когда родительский элемент имеет наименьший ключ.

6. union - операция объеденения, которая используется во многих других функциях, как вы могли наблюдать.

Data Science: Алгоритмы и Структуры данных

Китайская нейросеть, которая заменяет подписку на GPT — бесплатно и оффлайн

2026 год – новая эпоха для DeepSeek. Китайская нейросеть работает прямо на вашем устройстве, обгоняет западные модели и снимает все ограничения: без подписок, без интернета, без контроля.
Зерокодер обновил практикум и собрал все, что важно знать о локальных моделях и как с ними работать.

⚡️Что ждет вас на вебинаре?

– Покажем, как установить DeepSeek на компьютер и пользоваться нейросетью оффлайн, без подписки и передачи данных в облако;
– Объясним, чем отличаются версии DeepSeek и какие модели использовать для текста, кода, анализа данных, обучения и исследований;
– Проверим DeepSeek на реальных задачах: коде, документах, расшифровках созвонов и работе с собственными файлами;
– Покажем, как монетизировать навыки работы с локальными ИИ и как работать быстрее GPT бесплатно.

Регистрируйтесь прямо сейчас

Участники эфира получат чек-лист по выбору модели под задачу и подборку 20+ сценариев для ИИ-помощника на своем компьютере, который работает с вашими файлами.

Эфир подойдёт всем, кто хочет пользоваться ИИ без лимитов и зависимости от чужих серверов, монетизировать навыки и оставаться в тренде технологий 2026 года.

Бесплатный практикум – по ссылке.

Сортировка кучей (HeapSort)

Алгоритм сортировки в куче для сортировки в порядке возрастания:
1. Создайте максимальную кучу из входных данных.
2. На этом этапе самый большой элемент хранится в корне кучи. Замените его последним элементом кучи, а затем уменьшите размер кучи на 1. Наконец, скопируйте корень дерева.
3. Повторите шаг 2, пока размер кучи больше 1.

Data Science: Алгоритмы и Структуры данных