Please enable JavaScript.
Coggle requires JavaScript to display documents.
АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ (Графы (поиск в ширину (существует ли путь…
АЛГОРИТМЫ И
СТРУКТУРЫ ДАННЫХ
Поиск
простой поиск O(N)
Пробегаем по всем, сравниваем
бинарный поиск O(log(N))
Две функции: одна ищет левую границу, другая - правую. Поиск границы делением пополам и сравниванием.
Третья функция использует те две и выполняет поиск с выводом, который требуется.
Сортировка
Квадратичные сортировки O(N**2)
сортировка пузырьком (bubble sort)
сравниваем попарно слева направо
сортировка вставками (insert sort)
начинаем слева направо "расширять" массив: 1 элемент сам по себе отсортирован, второй сравниваем с первым - отсортированный массив из двух, третий "ведем" справа налево, пока не встретим меньше и т.д.
сортировка выбором (choise sort)
(сравниваем в цикле первый элемент со всеми (n раз))
ищем минимум сравниванием - он точно будет стоять на первом месте - убираем его из сортируемого массива
быстрая сортировка (Хоара), в среднем - O(n*log(n))
рекурсивно разбиваем массив на 2 части относительно случайного опорного элемента
все, что меньше опорного элемента - влево,
все что равно - на месте,
все что больше - вправо.
сортировка подсчетом O(N + M)
работает, когда много повторяющихся значений, самих значений немного и они известны
= частотный анализ
Доп. память: O(M), где M - число уникальных значений
Сортировка слиянием O(n*log(n))
делим массив пополам, сортируем их (рекуррентно)
делаем слияние двух отсортированных массивов в третий
Пирамидальная сортировка O(N*log(N))
строим из массива двоичную кучу
последовательно извлекаем максимальные элементы.
Графы
алгоритм Дейкстры: O(N**2)
для взвешенных графов
не работает с отрицательными весами
Цель: поиск кратчайших путей от исходной вершины ко всем
поиск в ширину
существует ли путь из A в B?
находит кратчайший путь
для невзвешенных графов
выполнение в очереди: FIFO
выделение компонент связности за O(N+M)
направленные и ненаправленные
обход в глубину
выделение (и подсчет) компоненты связности графа
проверка двудольности
поиск простого цикла
поиск мостов и точек сочленения
выделение компонент сильной связности (алгоритм Косарайо)
Топологическая сортировка. Алгоритм Тарьяна.
Алгоритм Флойда-Уоршелла O(N**3)
Цель: кратчайшее расстояние от каждой к каждой
Работает с отрицательными весами
(но не с циклами отрицательного веса)
Тип: динамическое программирование
Жадный алгоритм Дейкстры (тоже О(N**2)) - описан в википедии
NP-полные задачи O(N^P)
динамическое программирование
применяется для оптимизации некоторой характеристики
разбивает задачу на подзадачи, использует таблицы
значения ячеек - оптимизируемая характеристика
жадные алгоритмы
быстрое приближенное решение
локальная оптимизация в расчете на то, что в итоге будет достигнут глобальный минимум
Рекурсия
базовый и рекурсивный случаи
все вызовы сохраняются в стек
выполнение задач в стеке: LIFO
Хранение данных
массивы
быстрое чтение
питоновские листы
Занимают много места, данные хранятся разреженно
списки (связные!)
быстрая вставка и выполнение
реализация через класс
Хеш-таблицы
объединение хеш-функции и массива:
открытая хеш-таблица: в каждой ячейке ссылка на односвязный список
закрытая: в каждой ячейке массив - из-за этого проблемы с удалением
сведение к минимуму коллизий ( когда несколько элементов попадают имеют одинаковую хеш функцию)
очень быстрый поиск, вставка, удаление O(1)
кеширование данных, поиск дубликатов
элементы не упорядоченны, если элементов мало - быстрее создать список и по нему ходить
Куча / Пирамида
(Heap)
Быстрое добавление и извлечение элементов с максимальным приоритетом (например, максимальный по значению)
приоритет каждой вершины больше приоритетов её потомков.
заполнение уровней вершин идет сверху вниз
(в пределах одного уровня – слева направо).
Двоичную кучу удобно хранить в виде массива, левый потомок вершины с индексом i имеет индекс 2
i+1, а правый 2
i+2.
Корень дерева – элемент с индексом 0.
Высота двоичной кучи равна log2 N, где N – количество элементов массива.
Двоичное дерево поиска
Добавление и поиск за О(H: высота дерева)
~O(log(N)), когда дерево сбалансированное
Нужна балансировка