6 подписчиков

30 наиболее важных структур данных и алгоритмов

18 декабря 202018 дек 2020

42 мин

Алгоритмы и структуры данных (АСД) часто считаются пугающей темой — распространенным заблуждением.

Оглавление

Введение
Содержание
I. Структуры данных

Введение

Алгоритмы и структуры данных (АСД) часто считаются пугающей темой — распространенным заблуждением. Формируя основу самых инновационных концепций в области технологий, они необходимы как для соискателей на работу/стажировку, так и для опытных программистов. Освоение АСД подразумевает, что вы можете использовать свое вычислительное и алгоритмическое мышление для решения невиданных ранее проблем и внести свой вклад в ценность любой технологической компании (включая вашу собственную!). Понимая их, вы можете улучшить работоспособность, расширяемость и эффективность вашего кода.

Тем не менее, я решил сосредоточить все темы АСД, которые я публиковал в Twitter во время моего # 100DaysOfCode challenge Эта статья направлена на то, чтобы АСД не выглядели так устрашающе, как это считается. Она включает в себя 15 наиболее полезных структур данных и 15 наиболее важных алгоритмов, которые могут помочь вам пройти собеседование и улучшить свои навыки конкурентного программирования. Каждая глава содержит полезные ссылки с дополнительной информацией и практическими задачами. Темы СД сопровождаются графическим представлением и ключевой информацией. Каждый алгоритм реализован в постоянно обновляющемся репозитории Github. На момент написания статьи он содержит псевдокод, C++, Python и Java (всё еще находящиеся в стадии разработки) реализации каждого упомянутого алгоритма (и не только). Этот репозиторий расширяется благодаря другим талантливым и увлеченным разработчикам, которые вносят в него свой вклад, добавляя новые алгоритмы и новые реализации языков программирования.

Содержание

I. Структуры данных

Массивы
Связанные списки
Стеки
Очереди (queue)
Карты и Хэш-таблицы
Графы
Деревья
Бинарные деревья и Бинарные поисковые деревья
Самобалансирующиеся деревья (AVL Trees, Red-Black Trees, Splay Trees)
Кучи
Tries
Дерево сегментов
Деревья Фенвика
Система непересекающихся множеств
Минимальные Остовные Деревья

II. Алгоритмы

Разделяй и властвуй
Алгоритмы сортировки (Пузырьковая сортировка, Сортировка подсчетом, Быстрая Сортировка, Сортировка слиянием, Поразрядная сортировка (Radix Sort))
Алгоритмы поиска (Линейный поиск, Бинарный поиск)
Решето Эратосфена
Алгоритм Кнута-Морриса-Пратта
Жадный I-II (максимальное число неперекрывающихся интервалов на оси, задача о дробном рюкзаке)
Динамическое Программирование I (Задача о рюкзаке 0-1)
Динамическое программирование II (наибольшая общая подпоследовательность)
Динамическое программирование III (наибольшая возрастающая подпоследовательность)
Выпуклая оболочка
Обход Графа (Поиск По Ширине, Поиск По Глубине)
Алгоритм Флойда — Уоршелла / Рой—Флойда
Алгоритм Дейкстры и алгоритм Беллмана-Форда
Алгоритм Краскала
Топологическая сортировка

I. Структуры данных

1. Массивы

Массивы — это самые простые и распространенные структуры данных. Они характеризуются легким доступом элементов по индексу (позиции).

Для чего они используются?

Представьте себе ряд театральных стульев. Каждому стулу присвоено определенное положение (слева направо), поэтому каждому зрителю будет присвоен номер стула (стульев), на котором он будет сидеть. Это массив. Разверните задачу на весь театр (ряды и колонны стульев), и вы получите двумерный массив (матрицу)!

Свойства

значения элементов располагаются по порядку и доступны по их индексу от 0 до длины массива-1;
массив — это непрерывный блок памяти;
они обычно состоят из элементов одного типа (это зависит от языка программирования);
доступ и добавление элементов выполняются быстро; поиск и удаление не выполняются в O(1).

Полезные ссылки

2. Связанные списки

Связанные списки — это линейные структуры данных, как и массивы. Основное различие между связанными списками и массивами заключается в том, что элементы связанного списка не хранятся в смежных ячейках памяти. Состоят из узлов — сущностей, которые хранят значение текущего элемента и адресную ссылку на следующий элемент. Таким образом, элементы связаны указателями.

Для чего они используются?

Одним из важных применений связанных списков является реализация предыдущей и следующей страниц браузера. Двойной связанный список — это идеальная структура данных для хранения страниц, отображаемых при пользовательском поиске.

Свойства

они бывают трех типов: одиночные, двойные и круглые;
элементы не хранятся в непрерывном блоке памяти;
идеально подходит для отличного управления памятью (использование указателей подразумевает динамическое использование памяти);
вставка и удаление выполняются быстро; доступ и поиск элементов выполняются в линейном времени.

Полезные ссылки

3. Стеки

Стек — это абстрактный тип данных, формализующий концепцию коллекции с ограниченным доступом. Ограничение следует правилу LIFO (Last In — последний вход, First Out — первый выход). Таким образом, последний элемент, добавленный в стек, является первым элементом, который вы удаляете из него.

Стеки могут быть реализованы с помощью массивов или связанных списков.

Для чего они используются?

Самый распространенный пример из реальной жизни использует тарелки, расположенные одна над другой в столовой. Тарелка, которая находится наверху, снимается первой. Тарелка, расположенная в самом низу, — это та, которая остается в стопке в течение самого длительного периода времени.

Одна из ситуаций, когда стеки являются наиболее полезными, — это когда вам нужно получить обратный порядок заданных элементов. Просто сложите их все в стек(стопку), а затем удалите их — pop(Удаляет и возвращает элемент из стека).

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

Свойства

вы можете получить доступ только к последнему элементу за один раз (тот, что наверху);
одним из недостатков является то, что как только вы удаляете(pop) элементы сверху, чтобы получить доступ к другим элементам, их значения будут потеряны из памяти стека;
доступ к другим элементам осуществляется в линейном времени; любая другая операция выполняется в O(1).

Полезные ссылки

4. Очереди (queue)

Очередь — это еще один тип данных из коллекции ограниченного доступа, как и ранее рассмотренный стек. Главное отличие состоит в том, что очередь организована по модели FIFO (First In — первый вход, First Out — первый выход): первый вставленный элемент в очередь — это первый элемент, который должен быть удален. Очереди могут быть реализованы с помощью массива фиксированной длины, кругового массива или связанного списка.

Для чего они используются?

Наилучшим использованием этого абстрактного типа данных (АТД) является, конечно, моделирование реальной очереди. Например, в применении колл-центра очередь используется для сохранения клиентов, ожидающих помощи от консультанта — эти клиенты должны получать помощь в том порядке, в котором они звонили.

Одним из особых и очень важных типов очередей является приоритетная очередь. Элементы вводятся в очередь на основе связанного с ними "приоритета": элемент с наивысшим приоритетом вводится первым в очередь. Этот АТД необходим во многих графовых алгоритмах (алгоритм Дейкстры, BFS, алгоритм Прима, кодирование Хаффмана - подробнее о них ниже). Он реализуется с помощью кучи(heap).

Еще один особый тип очереди — deque (каламбур, произносится как "deck"). Элементы могут быть вставлены/удалены из обоих концов очереди.

Свойства

мы можем напрямую получить доступ только к "самому старому" введенному элементу;
поиск элементов удалит все доступные элементы из памяти очереди;
popping/pushing элементов или получение фронтальной части очереди происходит в постоянном времени. Поиск является линейным.

Полезные ссылки

5. Карты и Хэш-таблицы

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

Наиболее распространенной хеш-функцией (среди многих) является функция константы по модулю. Например, если константа равна 6, то значение ключа x равно x%6.

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

Для чего они используются?

Наиболее известным применением карт является словарь языка. Каждое слово из языка присвоило ему свое определение. Он реализован с помощью упорядоченной карты (ее ключи расположены в алфавитном порядке).

Контакты — это тоже карта. Каждому имени присвоен номер телефона.
Еще одно полезное применение — нормализация значений. Допустим, мы хотим присвоить каждой минуте дня (24 часа = 1440 минут) индекс от 0 до 1439. Хэш-функция будет иметь вид h(x) = x.hour*60+x.minute.

Свойства

ключи уникальны (никаких дубликатов);
сопротивление столкновению: должно быть трудно найти два разных входа с одним и тем же ключом;
pre-image сопротивление: рассматривая значение H, должно быть трудно найти ключ x, такой, что h(x)=H;
второе pre-image сопротивление: имея ключ и его значение, должно быть трудно найти другой ключ с таким же значением;
терминология:

* "карта(map)": Java, C++;

* "словарь": Python, JavaScript, .NET;

* "ассоциативный массив": PHP.

поскольку карты реализуются с использованием самобалансирующихся красно-чёрных деревьев (объяснено ниже), все операции выполняются в O(log n); все операции хэш-таблицы постоянны.

Полезные ссылки

Codeforces Problem Set

6. Графы

Граф — это нелинейная структура данных, представляющая собой пару двух множеств: G={V, E}, где V-множество вершин (узлов), а E-множество ребер (стрелок). Узлы — это значения, связанные между собой ребрами-линиями, которые изображают зависимость (иногда связанную со стоимостью/расстоянием) между двумя узлами.

Существует два основных типа графиков: ориентированные и неориентированные. В неориентированном графе ребро (x, y) доступно в обоих направлениях: (x, y) и (y, x). В ориентированном графе ребро (x, y) называется стрелкой, а направление задается порядком вершин в его названии: стрелка (x, y) отличается от стрелки (y, x).

Для чего они используются?

Графы — это основа любого типа сети: социальной сети (например, Facebook, LinkedIn) или даже сети улиц города. Каждый пользователь социальной медиа-платформы — это структура, содержащая все его персональные данные — она представляет собой узел сети. Instagram или Facebook — это ребра в неориентированном графе (потому что это взаимно), в то время как в Instagram или Twitter отношения между аккаунтом и его подписчиками/подписками — это стрелки в ориентированном графе (не взаимно).

Свойства

Теория графов — обширная область, но мы собираемся выделить несколько наиболее известных концепций:

степень узла в неориентированном графе — это число его падающих ребер;
внутренняя/внешняя степень узла в ориентированном графе — это количество стрелок, которые направляются в/из этого узла;
цепочка от узла x к узлу y представляет собой последовательность соседних ребер, причем x является ее левым концом, а y-правым;
цикл — это цепочка, где x=y; граф может быть циклическим/ациклическим; граф соединен, если существует цепочка между любыми двумя узлами из V;
граф может быть пройден и обработан с помощью поиска по ширине (BFS) или по глубине (DFS), как в O(|V|+|E|), где |S| — кардинальное множество S; Проверьте ссылки ниже для получения другой важной информации в теории графов.

Полезные ссылки

7. Деревья

Дерево — это неориентированный граф, минимальный с точки зрения связности (если мы исключим одно ребро, граф больше не будет связан) и максимальный с точки зрения ацикличности (если мы добавим одно ребро, граф больше не будет ациклическим). Таким образом, любой ациклический связный неориентированный граф является деревом, но для простоты мы будем называть корневые деревья деревьями.

Корень — это один фиксированный узел, который устанавливает направление ребер в дереве, так что именно там все "начинается". Листья — это конечные узлы дерева — вот где всё "заканчивается".
Дочерний элемент вершины — это её падающая вершина под ней. Вершина может иметь несколько дочерних элементов. Родитель вершины — это ее падающая вершина над ней-она уникальна.

Для чего они используются?

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

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

Свойства

у корня нет родителя;
у листьев нет дочерних элементов;
длина цепочки между корнем и узлом x представляет уровень x, на котором находится;
высота дерева — это его максимальный уровень (3 в нашем примере);
наиболее распространенным методом обхода дерева является DFS(поиск по глубине) в O (|V| + |E|), но мы также можем использовать BFS(поиск по ширине); порядок узлов, пройденных в любом графе с использованием DFS, формирует дерево DFS, которое указывает нам время посещения узла.

Полезные ссылки

8. Бинарные деревья и Бинарные поисковые деревья

Бинарное дерево — это особый тип дерева: каждая вершина может иметь максимум двух потомков. В строгом двоичном дереве каждый узел имеет ровно два дочерних элемента, за исключением листьев. Полное двоичное дерево с n уровнями имеет все 2ⁿ-1 возможных узла.

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

Для чего они используются?

Одним из важных применений бинарных деревьев является представление и оценка логических выражений. Каждое выражение может быть разложено на переменные/константы и операторы. Этот метод записи выражений называется обратной польской записью (ОПЗ). Таким образом, они могут сформировать двоичное дерево, где внутренние узлы являются операторами, а листья - переменными/константами — это называется абстрактным синтаксическим деревом (АСД).

Бинарные поисковые деревья часто используются из-за их быстрого поиска свойств ключей. AVL-деревья, красно-черные деревья, упорядоченные наборы и карты реализуются с помощью бинарных поисковых деревьев.

Свойства

существует три типа обходов DFS(поиск по глубине) для бинарных поисковых деревьев:

* Preorder (Root, Left, Right);

* Inorder (Left, Root, Right);

* Postorder (Left, Right, Root); всё сделано за O(n) времени;

обход по порядку дает нам все узлы в дереве в порядке возрастания;
самый левый узел — это минимальное значение в бинарных поисковых деревьях, а самый правый — максимальное;
обратите внимание, что ОПЗ является симметричным обходом АСД;
бинарные поисковые деревья имеют преимущества отсортированного массива, но недостаток логарифмической вставки — все его операции выполняются за O(log n) время.

Полезные ссылки

9. Самобалансирующиеся деревья

Все эти типы деревьев являются самобалансирующимися бинарными деревьями поиска. Разница заключается в том, как они уравновешивают свою высоту в логарифмическом времени.

Деревья AVL самобалансируются после каждой вставки/удаления, поскольку разница в модуле между высотами левого поддерева и правого поддерева узла составляет максимум 1. AVL названы в честь своих изобретателей: Адельсона-Вельского и Ландиса.

В красно-черных деревьях каждый узел хранит дополнительный бит, представляющий цвет, используемый для обеспечения баланса после каждой операции вставки/удаления.

В косые деревья, недавно просмотренные узлы могут быть быстро снова доступна, таким образом, амортизированная сложность любая операция-это все равно O(log n).

Для чего они используются?

AVL, по-видимому, является лучшей структурой данных в теории баз данных.

Красно-чёрные деревья используются для организации фрагментов сопоставимых данных, таких как текстовые фрагменты или числа. В версии Java 8 хэш-карты реализуются с помощью красно-чёрных деревьев. Структуры данных в вычислительной геометрии и функциональном программировании также строятся с помощью красно-чёрных деревьев.

Splay-деревья используются для кэшей, распределителей памяти, сборщиков мусора, сжатия данных, ropes (замена строки, используемой для длинных текстовых строк), в Windows NT (в виртуальной памяти, сети и коде файловой системы).

Свойства

амортизированная сложность ЛЮБОЙ операции в ЛЮБОМ самобалансирующимся бинарном дереве поиска равна O(log n);
максимальная высота AVL в худшем случае составляет 1,44 * log2n (почему? * подсказка: подумайте о случае AVL со всеми полными уровнями, кроме последнего, который имеет только один элемент);
AVL являются самыми быстрыми на практике для поиска элементов, но вращение поддеревьев для самобалансировки обходится дорого;
между тем, красно-чёрные деревья обеспечивают более быстрые вставки и удаления, потому что нет вращений;
Splay-деревья не нуждаются в хранении каких-либо бухгалтерских данных.

Полезные ссылки

10. Кучи

Мин-куча — это двоичное дерево, где каждый узел имеет свойство, что его значение больше или равно значению его родителя: val[par[x]] <= val[x], причем x — узел кучи, где val[x] — его значение, а par[x] — его родитель.

Существует также max-heap, который реализует противоположное отношение.

Двоичная куча — это полное двоичное дерево (все его уровни заполнены, за исключением, может быть, последнего уровня).

Для чего они используются?

Как мы уже обсуждали несколько дней назад, приоритетные очереди могут быть эффективно реализованы с помощью двоичной кучи, поскольку она поддерживает операции insert(), delete (), extractMax() и decreaseKey () за O(log n) времени. Таким образом, кучи также необходимы в графовых алгоритмах (из-за приоритетной очереди).

В любое время, когда вам понадобится быстрый доступ к максимальному/минимальному элементу, куча — это лучший вариант.

Кучи также являются основой алгоритма heapsort(пирамидальная сортировка или сортировка кучей).

Свойства

он всегда сбалансирован: всякий раз, когда мы удаляем/вставляем элемент в структуру, мы просто должны “sift”/”percolate”(отсеять) его, пока он не окажется в правильном положении;
родителем узла k > 1 является [k/2] (где [x] - целая часть x) , а его дочерними элементами являются 2*k и 2*k+1;
альтернативой приоритетной очереди являются set, ordered_map (в C++) или любая другая упорядоченная структура, которая может легко разрешить доступ к минимальному/максимальному элементу;
корень имеет приоритет, поэтому временная сложность его доступа равна O(1), вставка/удаление выполняются в O(log n); создание кучи выполняется в O(n); heapsort — в O(n*log n).

Полезные ссылки

GeeksforGeeks: Heaps

11. Tries

Trie — это эффективная структура данных информационного поиска. Также известный как префиксное дерево, это дерево поиска, которое позволяет вставлять и искать во временной сложности O(L), где L — длина ключа.

Если мы храним ключи в хорошо сбалансированном бинарном дереве поиска, то потребуется время, пропорциональное L * log n, где n — количество ключей в дереве. Таким образом, trie — это гораздо более быстрая структура данных (с O(L)) по сравнению с бинарным деревом поиска, но штраф зависит от требований к хранению trie.

Для чего они используются?

Trie в основном используется для хранения строк и их значений. Одно из его самых крутых применений — это автозаполнение и autosuggestions в строке поиска Google. Trie — лучший выбор, потому что это самый быстрый вариант: более быстрый поиск более ценен, чем хранилище, сохраненное, если мы не использовали trie.

Ортографическая автокоррекция набранных слов также выполняется с помощью trie, путем поиска слова в словаре или, возможно, других его экземпляров в том же тексте.

Свойства

он имеет ассоциацию ключ-значение; ключ обычно представляет собой слово или его префикс, но это может быть любой упорядоченный список;
корень(root) имеет пустую строку в качестве ключа;
разница в длине между значением узла и его дочерними значениями равна 1; таким образом, дочерние элементы корня будут хранить значение длины 1; в качестве вывода можно сказать, что узел x с уровня k имеет значение длины k;
как мы уже говорили, временная сложность операций вставки/поиска равна O(L), где L — длина ключа, что намного быстрее, чем O(log n) бинарного дерева поиска, но сравнимо с хэш-таблицей;
сложность пространства на самом деле является недостатком: O(ALPHABET_SIZE*L*n).

Полезные ссылки

12. Деревья сегментов

Дерево сегментов — это полное двоичное дерево, которое позволяет эффективно отвечать на запросы, но при этом легко изменять его элементы.

Каждый элемент индекса i в данном массиве представляет собой лист, помеченный интервалом [i, i]. Узел, имеющий свои дочерние элементы, помеченные [x, y], соответственно [y, z], будет иметь интервал [x, z] в качестве метки. Поэтому, учитывая n элементов (0-индексированных), корень дерева сегментов будет помечен [0, n-1].

Для чего они используются?

Они чрезвычайно полезны в задачах, которые могут быть решены с помощью "Разделяй и властвуй" (первая концепция алгоритмов, которую мы хотим обсудить), а также может потребоваться обновление их элементов. Таким образом, при обновлении элемента любой интервал, содержащий его, также изменяется, поэтому сложность является логарифмической. Например, сумма/максимум/минимум n заданных элементов являются наиболее распространенными применениями сегментных деревьев. Двоичный поиск также может использовать дерево сегментов, если обновления элементов происходят случайно.

Свойства

будучи двоичным деревом, узел x будет иметь 2*x и 2*x+1 в качестве потомков и [x/2] в качестве родителя, где [x] — целая часть x;
один эффективный метод обновления всего диапазона в дереве сегментов называется "ленивым распространением", и он также выполняется в O(log n) (см. ссылки ниже для реализации операций);
они могут быть k-мерными : например, имея q запросов на нахождение суммы заданных подматриц одной матрицы, мы можем использовать 2-мерное сегментное дерево;
обновление элементов/диапазонов требует O(log n) времени; ответ на запрос является постоянным (O(1));
сложность пространства линейна, что является большим преимуществом: O(4*n).

Полезные ссылки

13. Деревья Фенвика

Дерево Фенвика, также известное как двоичное индексированное дерево (ДИД), представляет собой структуру данных, которая также используется для эффективных обновлений и запросов. По сравнению с сегментными деревьями ДИД требуют меньше места и проще реализуются.

Для чего они используются?

Двоичные индексированные деревья используются для вычисления префиксных сумм — префиксная сумма элемента на позиции i является суммой элементов от первой позиции до i. Они представлены с помощью массива, где каждый индекс представлен в двоичной системе. Например, индекс 10 эквивалентен индексу 2 в десятичной системе.

Свойства

построение дерева — самая интересная часть: во-первых, массив должен быть 1-индексирован; чтобы найти родителя узла x, вы должны преобразовать его индекс x в двоичную систему и flip'нуть самый правый знаменательный бит; например, родитель узла 6 - это 4; 6 = 1*2²+1*2¹+0*2⁰ => 1"1"0(flip)=> 100 = 1*2²+0*2¹+0*2⁰ = 4;
наконец, конечные элементы, каждого узла должны содержать интервал, который может быть добавлен к префиксной сумме (подробнее о построении и реализации в ссылках ниже);
временная сложность по-прежнему составляет O(log n) для обновлений и O(1) для запросов, но пространственная сложность имеет еще большее преимущество: O(n), по сравнению с O(4*n) дерева сегментов.

Полезные ссылки

14. Система непересекающихся множеств

Нам даны n элементов, каждый из которых представляет собой отдельный набор. Системы непересекающихся множеств (СНМ) позволяют выполнить две операции:

UNION — объединение любых двух наборов (или объединение наборов двух разных элементов, если они не из одного набора);
FIND — поиск набора, из которого происходит элемент.

Для чего они используются?

СНМ очень важны в теории графов. Вы можете проверить, происходят ли две вершины из одного и того же связного компонента или, возможно, даже объединить два связанных компонента.
Давайте возьмем пример городов и поселков. Поскольку соседние города с демографическим и экономическим ростом расширяются, они могут легко создать мегаполис. Поэтому два города объединяются и их жители живут в одном мегаполисе. Мы также можем проверить, в каком городе живет человек, вызвав функцию FIND.

Свойства

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

Полезные ссылки

15. Минимальные остовные деревья

Для связного и ненаправленного графа остовное дерево этого графа является подграфом, который является деревом и соединяет все вершины вместе. В одном графе может быть много разных связующих деревьев.

Минимальное остовное дерево (МОД) для взвешенного, связного и ненаправленного графа — это остовное дерево с весом, меньшим или равным весу любого другого остовного дерева. Вес остовного дерева — это сумма весов, присвоенных каждому ребру остовного дерева.

Для чего они используются?

Цель МОД — это задача оптимизации и задача минимальных затрат. Имея сеть маршрутов, можно считать, что одним из факторов, влияющих на установление государственного маршрута между n городами, является минимальное расстояние между двумя соседними городами.

Таким образом, государственный маршрут представлен как МОД графа дорожной сети.

Свойства

будучи деревом, МОД графа с n вершинами имеет n-1 ребер; его можно решить с помощью:

* Алгоритм Прима-лучший вариант для плотных графов (графы с n
узлами и числом ребер близки к n(n-1)/2);

* Алгоритм крускала-в основном используется; это жадный алгоритм,
основанный на системе непересекающихся множеств (мы
также обсудим его);

временная сложность его построения составляет O(n log n) или O(n log m) для Крускала(это зависит от графа) и O(n²) для Прима.

Полезные ссылки

II. Алгоритмы

1. Разделяй и властвуй

Разделяй и властвуй (РиВ) - это не конкретный алгоритм сам по себе, а важная категория алгоритмов, которую необходимо понять, прежде чем погружаться в другие темы. Он используется для решения задач, которые можно разделить на подзадачи, аналогичные исходной задаче, но меньшие по размеру. Затем РиВ рекурсивно решает их и, наконец, объединяет результаты, чтобы найти решение проблемы.

Она имеет три стадии:

Divide(разделяй) — задачи в подзадачи;
Conquer(властвуй) — подзадачи с применением рекурсии;
Merge(объединение, слияние) — результаты подзадач переходят в окончательное решение.

Для чего это используется?

Одним из практических применений РиВ является параллельное программирование с использованием нескольких процессоров, поэтому подзадачи выполняются на разных машинах.

РиВ является основой многих алгоритмов, таких как быстрая сортировка, сортировка слиянием, двоичный поиск или алгоритмы быстрого умножения.

Свойства

каждая задача DAC может быть записана как рекуррентное отношение; поэтому важно найти базовый случай, который останавливает рекурсию;
его сложность равна T(n)=D(n)+C(n)+M(n), что означает, что каждый этап имеет разную сложность в зависимости от задачи.

Полезные ссылки

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

Алгоритм сортировки используется для перестановки заданных элементов (из массива или списка) в соответствии с оператором сравнения элементов. Когда мы обращаемся к отсортированному массиву, мы обычно думаем о порядке возрастания (оператор сравнения "<"). Существуют различные типы сортировки, с различными временными и пространственными сложностями. Некоторые из них основаны на сравнении, другие — нет. Вот самые популярные/эффективные методы сортировки:

Пузырьковая сортировка

Пузырьковая сортировка — один из самых простых алгоритмов сортировки. Он основан на повторном обмене между соседними элементами, если они находятся в неправильном порядке. Он стабилен, его временная сложность составляет O(n²), и ему нужно O(1) вспомогательное пространство.

Bubble Sort Visualization

Сортировка подсчетом

Сортировка подсчетом — это не сортировка, основанная на сравнении. Этот алгоритм в основном использует частоту каждого элемента (своего рода хэширование), определяет минимальное и максимальное значение, а затем выполняет итерацию между ними, чтобы разместить каждый элемент в зависимости от его частоты. Это делается в O(n), а пространство пропорционально диапазону данных. Это эффективно, если диапазон ввода данных незначительно превышает количество элементов.

Counting Sort Visualization

Быстрая сортировка

Быстрая сортировка — это применение "Разделяй и властвуй". Алгоритм основан на выборе элемента в качестве опорного (первого, последнего или медианного), а затем замене элементов, чтобы поместить опорный элемент между всеми элементами, меньшими, чем он, и всеми элементами, большими, чем он. Он не имеет дополнительного пространства и временной сложности O(n*log n) — наилучшей сложности для методов, основанных на сравнении.

Вот демонстрация с выбором опорного элемента в качестве последнего:

Quick Sort Visualization

Сортировка слиянием

Сортировка слиянием также является применением «Разделяй и властвуй». Алгоритм делит массив на две половины, сортирует каждую половину и затем объединяет их. Его временная сложность также составляет O(n*log n), поэтому он также очень быстр, как и быстрая сортировка, но, к сожалению, ему требуется O(n) дополнительного пространства для одновременного хранения двух подмассивов и, наконец, их слияния.

Merge Sort Visualization

Поразрядная сортировка (Radix Sort)

Radix Sort использует сортировку подсчётом в качестве подпрограммы, поэтому это не алгоритм, основанный на сравнении. Откуда мы знаем, что сортировки подсчетом недостаточно? Предположим, нам нужно отсортировать элементы в [1, n²]. Используя сортировку подсчётом, нам потребуется O(n²). Нам нужен линейный алгоритм - O(n + k), где элементы находятся в диапазоне [1, k]. Он сортирует элементы по цифрам, начиная с наименьшего значащего (единицы), до наибольшего (десятки, сотни и т. Д.). Дополнительный пространство (из сортировки подсчётом): O(n).

Radix Sort Visualization

Полезные ссылки

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

Алгоритмы поиска предназначены для проверки наличия элемента в структуре данных и даже его возврата. Есть несколько методов поиска, но вот самые популярные два:

Линейный поиск

Подход этого алгоритма очень прост: вы начинаете поиск своего значения с первого индекса структуры данных(СД). Вы сравниваете их один за другим, пока ваше значение и ваш текущий элемент не сравняются. Если этого конкретного значения нет в СД, вернуть -1.

Временная сложность: O(n)

Бинарный поиск

Бинарный поиск — это один из эффективных алгоритмов поиска, основанный на принципе "Разделяй и Властвуй". К сожалению, он работает только с отсортированными структурами данных. Используя метод РиВ, вы постоянно разделяете структуру данных на две половины и сравниваете своё значение в поиске со значением среднего элемента. Если они равны, поиск завершен. В любом случае, если ваше значение больше/меньше, поиск должен продолжаться на правой/левой половине.
Временная сложность: O(log n)

Полезные ссылки

4. Решето Эратосфена

Для целого числа n выведите все простые числа, меньшие или равные n.

Решето Эратосфена - один из самых эффективных алгоритмов, решающих эту проблему, и он отлично работает для n меньше 10.000.000.

В методе используется список/карта частот, которые отмечают простоту каждого числа в диапазоне [0, n]: ok[x] = 0, если x является простым, ok[x] = 1 в противном случае.
Мы начинаем выбирать каждое простое число из нашего списка и отмечать его кратные из списка цифрой 1 - таким образом мы выбираем немаркированные (0) числа. Наконец, мы можем легко ответить за O(1) на любое количество запросов.

Классический алгоритм важен для многих применений, но мы можем сделать несколько оптимизаций. Во-первых, мы можем легко заметить, что 2 — единственное четное простое число, поэтому мы можем проверить его кратные по отдельности, а затем выполнить итерацию в диапазоне, чтобы найти простые числа от двух до двух. Во-вторых, очевидно, что для числа x мы ранее проверяли 2x, 3x, 4x и т.д., Когда мы перебирали 2, 3 и т.д. Таким образом, наша многократная проверка цикла может каждый раз начинаться с x². Наконец, даже половина этих кратных чисел является четной, и мы также перебираем нечетные простые числа, поэтому мы можем легко перебирать просто от 2 * x до 2 * x в цикле проверки кратных.

Пространственная сложность: O(n)
Временная сложность: O(n*log(log n)) для классического алгоритма, O(n) для оптимизированного.

Почему O(n*log(log n))?
Ответ

Полезные ссылки

Sieve of Eratosthenes Implementation

5. Алгоритм Кнута-Морриса-Пратта

Для текста длины n и шаблона длины m найдите все вхождения шаблона в тексте.

Алгоритм Кнута-Морриса-Пратта (КМП) является эффективным способом решения проблемы сопоставления с шаблоном.
Наивное решение основано на использовании «скользящего окна», в котором мы сравниваем символ с символом каждый раз, когда устанавливаем новый начальный индекс, начиная с индекса 0 текста до индекса n-m. Таким образом, временная сложность составляет O(m*(n-m+1))~O(n*m).

КМП — это оптимизация наивного решения: она выполняется за O(n) и лучше всего работает, когда в шаблоне много повторяющихся подшаблонов. Таким образом, он также использует скользящее окно, но вместо того, чтобы сравнивать все символы с подстрокой, он постоянно ищет самый длинный суффикс текущего подшаблона, который также является его префиксом. Другими словами, каждый раз, когда мы обнаруживаем несоответствие после некоторых совпадений, мы уже знаем некоторые символы в тексте следующего окна. Следовательно, сравнивать их снова бесполезно, поэтому мы перезапускаем сопоставление с тем же символом в тексте с символом после этого префикса. Как узнать, сколько символов нужно пропустить? Что ж, мы должны создать массив предварительной обработки, который сообщает нам, сколько символов следует пропустить.

Полезные ссылки

6. Жадный метод

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

При этом при использовании жадного метода оптимальное решение на каждом этапе приводит к общему оптимальному решению. Однако в большинстве случаев решение, которое мы принимаем на одном этапе, влияет на список решений для следующего этапа. В этом случае алгоритм должен быть продемонстрирован математически. Жадный метод также дает отличные решения для некоторых математических задач, но не для всех (возможно, наиболее оптимальное решение не гарантируется)!

Жадный алгоритм обычно состоит из пяти компонентов:

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

Задача о дробном рюкзаке

Учитывая вес и значение n элементов, нам нужно положить эти элементы в рюкзак вместимостью W, чтобы получить максимальное общее значение в рюкзаке (разрешается брать фрагменты элементов: значение фрагмента пропорциональна его весу).

Основная идея жадного подхода — сортировать все элементы по соотношению значение/вес. Затем мы можем добавить столько целых элементов, сколько сможем. В тот момент, когда мы обнаружим элемент тяжелее (w2), чем наш доступный вес, оставшийся в рюкзаке (w1), мы разделим его на части: возьмем только w2-w1, чтобы максимизировать нашу прибыль. Гарантируется, что это жадное решение верное.

Полезные ссылки

7. Динамическое программирование

Динамическое программирование (ДП) — это аналогичный подход к "Разделяй и Властвуй". Он также разбивает проблему на похожие подзадачи, но на самом деле они перекрываются и взаимозависимы - они не решаются независимо.

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

Приминения ДП включают ряд чисел Фибоначчи, Ханойскую башню, Рой-Флойд-Уоршелл, Дейкстра и т. Д. Ниже мы собираемся обсудить решение ДП задачи о рюкзаке 0–1.

Задача о рюкзаке 0-1

Учитывая веса и значения n предметов, нам нужно положить эти элементы в рюкзак вместимостью W, чтобы получить максимальное общее значение в рюкзаке (дробление элементов, как в решении жадного метода, не допускается).

Свойство 0–1 обусловлено тем фактом, что мы должны либо выбрать весь элемент, либо не выбирать его вообще.
Мы строим структуру ДП в виде матрицы dp[i][cw], хранящей максимальный профит, который мы можем получить, выбрав i объектов, общий вес которых равен cw. Легко заметить, что сначала мы должны инициализировать dp[1][w[i]] с помощью v[i], где w[i] — вес объекта i, а v[i] — его значение.
Повторяемость следующая: dp[i][cw] = max(dp[i-1][cw], dp[i-1][cw-w[i]] + v[i]). Давайте разберемся немного.

dp[i-1][cw] показывает случай, когда мы не добавляем текущий элемент в рюкзак. dp[i-1][cw-w[i]] + v[i] — это случай, когда мы добавляем элемент. При этом dp[i-1][cw-w[i]] — это максимальная прибыль от взятия i-1 элементов: поэтому их вес равен текущему весу без веса нашего элемента. Наконец, мы добавляем к нему значение нашего элемента.
Ответ сохраняется в dp[n][W]. Оптимизация выполняется с помощью простого наблюдения: при повторении текущая строка (ряд) зависит только от предыдущей строки. Следовательно, хранить структуру ДП в матрице не нужно, поэтому мы должны выбрать массив для лучшей пространственной сложности: O(n). Временная сложность: O(n * W).

Полезные ссылки

0–1 Knapsack Problem Implementation

8. Наибольшая общая подпоследовательность(НОП)

Для двух последовательностей найдите длину самой длинной подпоследовательности, присутствующей в обеих из них. Подпоследовательность - это последовательность, которая появляется в одном и том же относительном порядке, но не обязательно непрерывно. Например, «bcd», «abdg», «c» являются подпоследовательностями «abcdefg».

Вот еще одно применение динамического программирования. Алгоритм НОП использует ДП для решения задачи сверху.

Фактическая подзадача состоит в том, чтобы найти наибольшую общую подпоследовательность, которая начинается с индекса i в последовательности A, соответственно с индекса j в последовательности B.

Далее мы построим структуру ДП — lcs[][](матрицу), где lcs[i][j] — максимальная длина общей подпоследовательности, которая начинается с индекса i в A, соответственно индекса j в B. Мы собираемся строить его сверху вниз. Решение, очевидно, хранится в lcs[n][m], где n — длина A, а m — длина B.

Отношение рекуррентности довольно простое и интуитивно понятное. Для простоты мы будем считать, что обе последовательности имеют 1-индекс. Во-первых, мы собираемся инициализировать lcs[i][0], 1 <= i <= n, и lcs[0][j], 1 <= j <= m, с 0 в качестве базовых случаев (нет подпоследовательности, начинающейся с 0). Далее рассмотрим два основных случая: если A[i] равно B[j], то lcs[i][j] = lcs[i-1][j-1]+1 (еще один идентичный символ, чем предыдущий НОП). В противном случае это будет максимум между lcs[i-1][j] (если A[i] не принимается во внимание) и lcs[i][j-1] (если B[j] не принимается во внимание ).

Временная сложность: O(n*m)

Дополнительное пространство: O(n*m)

Полезные ссылки

LCS Implementation

9. Наибольшая возрастающая подпоследовательность(НВП)

Для последовательности A из n элементов найдите длину наибольшей подпоследовательности, чтобы все ее элементы были отсортированы в порядке возрастания. Подпоследовательность — это последовательность, которая появляется в одном и том же относительном порядке, но не обязательно непрерывно. Например, «bcd», «abdg», «c» являются подпоследовательностями «abcdefg».

НВП — еще одна классическая задача, которую можно решить с помощью динамического программирования.

Нахождение НВП выполняется с использованием массива l[] в качестве структуры ДП, где l[i] — максимальная длина возрастающей подпоследовательности, содержащей A[i], имеющую свои элементы из [A [i],…, A [n]] подпоследовательность. l[i] равно 1, если все элементы после A[i] меньше его. В противном случае максимальное значение 1+ между всеми элементами после A[i], которые больше его. Очевидно, l[n] = 1, где n — длина A. Реализация выполняется снизу вверх (начиная с конца).

Одна проблема оптимизации возникает при поиске максимума между всеми элементами после текущего элемента. Лучшее, что мы можем сделать, — это выполнить двоичный поиск максимального элемента.

Чтобы также найти подпоследовательность известной теперь максимальной длины, нам просто нужно использовать дополнительный массив ind[], в котором хранится индекс каждого максимального значения.

Сложность времени: O(n*log n)

Дополнительное пространство: O(n)

Полезные ссылки

LIS Implementation

10. Выпуклая оболочка

Дан набор из n точек в одной плоскости, найдите выпуклый многоугольник с минимальной площадью, который содержит все заданные точки (расположенные внутри многоугольника или по его сторонам). Такой многоугольник называется выпуклой оболочкой. Задача выпуклой оболочки — это классическая геометрия, которая имеет множество применений в реальной жизни. Например, предотвращение столкновений: если выпуклый корпус автомобиля избегает столкновений, то и автомобиль тоже. Расчет путей производится с использованием выпуклых изображений автомобилей. Анализ формы также выполняется с помощью выпуклой оболочки. Таким образом, обработка изображений легко выполняется путем сопоставления моделей по их выпуклому дереву дефектов.

Есть несколько алгоритмов, используемых для поиска выпуклой оболочки, например алгоритм Джарвиса, сканирование Грэма и т.д. Сегодня мы собираемся обсудить сканирование Грэма и некоторые полезные оптимизации.

Сканирование Грэма сортирует точки по их полярному углу — наклон линии, определяемый определенной точкой и другими выбранными точками. Затем используется стек для хранения выпуклой оболочки в текущий момент. Когда точка x помещается в стек, другие точки будут выталкиваться из стека, пока точка x и линия, определяемая двумя последними точками, не сформируют угол меньше 180°. Наконец, последняя точка, введенная в стек, закрывает многоугольник. Этот подход имеет временную сложность O(n*log n) из-за сортировки. Однако этот метод может привести к ошибкам точности при вычислении наклона.

Одно улучшенное решение с такой же временной сложностью, но с меньшими ошибками сортирует точки по их координатам (x, затем y). Затем мы рассматриваем линию, образованную крайней левой и крайней правой точками, и задача делится на две подзадачи. Наконец, мы находим выпуклую оболочку по обе стороны от линии. Выпуклая оболочка всех данных точек — это соединение двух оболочек.

Полезные ссылки

Convex Hull Implementation

11. Обход графа

Задача обхода графов связана с посещением всех узлов в определенном порядке, обычно вычисляя другую полезную информацию по пути.

Поиск по ширине

Алгоритм поиска по ширине (BFS) — один из наиболее распространенных способов определить, связан ли граф или нет, или, другими словами, найти связный компонент исходного узла BFS.

BFS также используется для вычисления кратчайшего расстояния между исходным узлом и всеми остальными узлами. Другая версия BFS — это алгоритм Ли, используемый для вычисления кратчайшего пути между двумя ячейками в сетке.

Алгоритм начинается с посещения исходного узла, а затем его соседей, которые помещаются в очередь. Выскакивает первый элемент из очереди. Мы посетим всех его соседей и поместим в очередь тех, которые ранее не посещались. Процесс повторяется до тех пор, пока очередь не опустеет. Когда очередь становится пустой, это означает, что все достижимые вершины были посещены и алгоритм завершается.

Поиск по глубине

Алгоритм поиска по глубине(DFS) — еще один распространенный метод обхода. На самом деле это лучший вариант, когда дело доходит до проверки связности графика.

Сначала мы посещаем корневой узел и помещаем его в стек. Пока стек не пустой, исследуем узел вверху. Если у узла есть не посещённые соседи, один из них выбирается и помещается в стек. В противном случае, если были посещены все его соседи, мы выталкиваем узел. Когда стек становится пустым, алгоритм завершается.

После такого обхода формируется дерево DFS. Дерево DFS имеет множество применений; один из наиболее распространенных — это сохранение «начального» и «конечного» времени каждого узла — момента, когда он попадает в стек, или, соответственно, момента, когда он выталкивается из него.

Полезные ссылки

12. Алгоритм Флойда — Уоршелла

Алгоритм Флойда-Уоршелла/Роя-Флойда решает задачу кратчайшего пути для всех пар: найти кратчайшие расстояния между каждой парой вершин в заданном ориентированном графе, взвешенном по ребрам.

Алгоритм Флойда-Уоршелла — это применение динамического программирования. Структура ДП(матрица) dist[][] инициализируется входной матрицей графа. Затем мы рассматриваем каждую вершину как промежуточное звено между двумя другими узлами. Кратчайшие пути обновляются между каждыми двумя парами узлов, при этом любой узел k является промежуточной вершиной. Если k является промежуточным звеном в наиболее подходящем пути между i и j, то dist[i][j] становится максимумом между dist[i][k] + dist[k][j] и dist[i][j].
Временная сложность: O(n³)
Пространственная сложность: O(n²)

Полезные ссылки

FW Implementation

13. Алгоритм Дейкстры и алгоритм Беллмана-Форда

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

Для данного графа и исходной вершины в графе найдите кратчайшие пути от источника ко всем вершинам данного графа.

Алгоритм Дейкстры используется для поиска таких путей во взвешенном графе, где все веса положительны.

Dijkstra - это жадный алгоритм, который использует дерево кратчайших путей (SPT) с исходным узлом в качестве корня. SPT — это самобалансирующееся двоичное дерево, но алгоритм может быть реализован с использованием кучи (или очереди с приоритетами). Мы собираемся обсудить решение кучи, потому что его временная сложность составляет O(|E| * log |V|). Идея состоит в том, чтобы работать со списком смежности графа. Таким образом, узлы будут пройдены за O(|V| + |E|) времени с использованием BFS.

Все вершины проходят с помощью BFS, а те, для которых кратчайшее расстояние еще не определено, сохраняются в Min-Heap (очередь приоритетов).

Создается Min-Heap, и каждый узел помещается в нее вместе со своими значениями расстояния. Затем источник становится корнем кучи с расстоянием 0. Остальным узлам будет назначено бесконечное расстояние. Пока куча не пуста, мы извлекаем минимальное значение расстояния узла x. Для каждой вершины y, смежной с x, мы проверяем, находится ли y в Min-Heap. В этом случае, если значение расстояния больше, чем вес (x, y) плюс значение расстояния x, то мы обновляем значение расстояния y.

Алгоритм Беллмана-Форда

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

Беллман-Форд хорошо подходит для распределенных систем, хотя его временная сложность составляет O(|V||E|).

Мы инициализируем dist[] точно так же, как в Дейкстра. Для *|V|-1 раз для каждого (x, y) ребра, если dist[y] > dist[x] + вес (x, y), то мы обновляем dist[y] с его помощью.

Мы повторяем последний шаг, чтобы, возможно, найти отрицательный цикл. Идея состоит в том, что последний шаг гарантирует минимальное расстояние, если нет отрицательного цикла. Если есть какой-либо узел, который имеет более короткое расстояние на текущем шаге, чем на последнем, то был обнаружен отрицательный цикл.

Полезные ссылки

14. Алгоритм Краскала

Ранее мы обсуждали, что такое минимальное связующее дерево.

Существует два алгоритма, которые определяют минимальное связующее дерево графа: Прим (полезно для плотных графов) и Краскал (идеально для большинства графов). Теперь мы собираемся обсудить алгоритм Краскала.

Краскал разработал жадный алгоритм для поиска минимального связующего дерева. Он эффективен на редких графах, потому что его временная сложность составляет O(|E| * log |V|).

Подход алгоритма следующий: мы сортируем все ребра в порядке возрастания их веса. Затем выбирается самое маленькое ребро. Если он не образует цикл с текущим минимальным связующим деревом, мы включаем его. В противном случае выбросьте его. Последний шаг повторяется до тех пор, пока в минимальном связующем дереве не будет |V|-1 ребер.

Включение ребер в минимальное связующее дерево выполняется с помощью Системы Непересекающихся Множеств, что также обсуждалось ранее.

Полезные ссылки

Kruskal Implementation

15. Топологическая сортировка

Ориентированный ациклический граф (DAG) — это просто ориентированный граф, который не содержит циклов.

Топологическая сортировка в DAG — это линейное упорядочение вершин таким образом, что для каждой дуги (x, y) узел x предшествует узлу y.

Очевидно, что первая вершина в топологической сортировке - это вершина с нулевой внутренней степенью (к ней нет направляющих дуг).

Еще одно особое свойство состоит в том, что DAG не имеет уникальной топологической сортировки.

Реализация BFS следует этой процедуре: обнаруживается узел с нулевой внутренней степенью, который первым отправляет на сортировку. Эта вершина удаляется из графа. Поскольку новый граф также является DAG, мы можем повторить процесс.

В любой момент во время DFS узел может принадлежать к одной из этих трех категорий:

узлы, которые мы закончили посещать (извлеченные из стека);
узлы, которые в данный момент находятся в стеке;
узлы, которые еще предстоит обнаружить.

Если во время DFS в группе DAG узел x имеет выходящую ребро к узлу y, тогда y находится либо в первой, либо в третьей категории. Если y был в стеке, то (x, y) завершил бы цикл, что противоречит определению DAG.

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

Полезные ссылки

Topological Sorting Implementation

Вау, вы дочитали до конца статьи. Спасибо за внимание! :) Удачного кодинга!

Перевод

Источник