Эти алгоритмы необходимы каждому программисту
Будучи студентом, изучающим программирование, вы, скорее всего, изучили множество различных алгоритмов на протяжении всей своей карьеры. Владение различными алгоритмами является абсолютно необходимым для любого программиста
При таком количестве алгоритмов может быть сложно уследить за тем, какой из них является основным. Если вы готовитесь к собеседованию или просто совершенствуете свои навыки, этот список поможет вам сделать это относительно легко. Читайте дальше, так как мы перечислили самые необходимые алгоритмы для программистов
1. Алгоритм Дейкстры
Эдсгер Дейкстра был одним из самых влиятельных компьютерных ученых своего времени, он внес вклад во многие различные области вычислительной техники, включая операционные системы, создание компиляторов и многое другое. Одним из наиболее заметных вкладов Дейкстры является изобретательность его алгоритма кратчайшего пути для графов, также известного как алгоритм кратчайшего пути Дейкстры
Алгоритм Дейкстры находит единственный кратчайший путь в графе от источника до всех вершин графа. На каждой итерации алгоритма добавляется вершина с минимальным расстоянием от источника и вершина, которая не существует в текущем кратчайшем пути. Это свойство жадности используется алгоритмом Джикстры
Алгоритм обычно реализуется с помощью множества. Алгоритм Дейкстры очень эффективен при реализации с Min Heap; вы можете найти кратчайший путь всего за O(V+ElogV) времени (V – количество вершин и E – количество ребер в данном графе)
Алгоритм Дейкстры имеет свои ограничения; он работает только на направленных и неориентированных графах с ребрами положительного веса. Для отрицательных весов алгоритм Беллмана-Форда обычно предпочтительнее
Вопросы на собеседовании часто включают алгоритм Джикстры, поэтому мы настоятельно рекомендуем разобраться в его тонкостях и приложениях
2. Сортировка слиянием
В этом списке есть несколько алгоритмов сортировки, и сортировка слиянием – один из самых важных алгоритмов. Это эффективный алгоритм сортировки, основанный на технике программирования ‘Разделяй и властвуй’. В худшем случае сортировка слиянием может отсортировать “n чисел всего за O(nlogn) времени. По сравнению с примитивными методами сортировки, такими как Bubble Sort (которая занимает O(n^2) времени), сортировка слиянием является чрезвычайно эффективной
Похожие: Введение в алгоритм сортировки слиянием
При сортировке слиянием массив, подлежащий сортировке, многократно разбивается на подмассивы, пока каждый подмассив не будет состоять из одного числа. Затем рекурсивный алгоритм многократно объединяет подмассивы и сортирует массив
3. Зыбкая сортировка
Quicksort – это еще один алгоритм сортировки, основанный на технике программирования ‘Разделяй и властвуй’. В этом алгоритме сначала выбирается элемент в качестве стержня, а затем весь массив разбивается вокруг этого стержня
Как вы уже догадались, хороший стержень имеет решающее значение для эффективной сортировки. Поворотным элементом может быть случайный элемент, элемент носителя, первый элемент или даже последний элемент
Реализации сортировки quicksort часто различаются по способу выбора стержня. В среднем случае quicksort отсортирует большой массив с хорошей поворотной точкой всего за O(nlogn) времени
Общий псевдокод quicksort многократно разделяет массив по стержню и помещает его в нужную позицию подмассива. Он также размещает элементы меньше поворотного слева от него, а элементы больше поворотного справа от него
4. Поиск по глубине
Поиск в глубину (DFS) – один из первых алгоритмов работы с графами, который преподается студентам.DFS – это эффективный алгоритм, используемый для обхода или поиска графа. Он также может быть модифицирован для использования в обходе деревьев
Обход DFS может начинаться с любой произвольной вершины, и он погружается в каждую соседнюю вершину. Алгоритм возвращается назад, если нет ни одной непосещенной вершины, или если есть тупик.DFS обычно реализуется со стеком и булевым массивом для отслеживания посещенных вершин.DFS проста в реализации и исключительно эффективна; она работает(V+E), где V – количество вершин, а E – количество ребер
Типичные приложения обхода DFS включают топологическую сортировку, обнаружение циклов в графе, поиск путей и сильно связных компонентов
5. Поиск по ширине
Breadth-First Search (BFS) также известен как обход деревьев по порядку уровней.BFS работает за O(V+E), подобно алгоритму DFS. Однако BFS использует очередь вместо стека.DFS погружается в граф, в то время как BFS обходит граф по ширине
Алгоритм BFS использует очередь для отслеживания вершин. Непосещенные соседние вершины посещаются, помечаются и ставятся в очередь. Если у вершины нет ни одной смежной вершины, то вершина удаляется из очереди и исследуется
BFS широко используется в одноранговых сетях, для нахождения кратчайшего пути в невзвешенном графе и для нахождения минимального прячущегося дерева
6. Бинарный поиск
Двоичный поиск – это простой алгоритм для поиска нужного элемента в отсортированном массиве. Он работает путем многократного деления массива пополам. Если требуемый элемент меньше среднего элемента, то дальше обрабатывается левая часть среднего элемента, в противном случае правая часть делится пополам и снова выполняется поиск. Процесс повторяется до тех пор, пока не будет найден требуемый элемент
В наихудшем случае временная сложность двоичного поиска равна O(logn), что делает его очень эффективным при поиске в линейных массивах
7. Алгоритмы минимального связующего дерева
Минимальное связующее дерево (MST) графа имеет минимальную стоимость среди всех возможных связующих деревьев. Стоимость дерева зависит от веса его ребер. Важно отметить, что может существовать более одного минимального остовного дерева. Существует два основных алгоритма MST, а именно алгоритм Крускала и алгоритм Прима
Алгоритм Крускала создает MST путем добавления ребра с минимальной стоимостью к растущему множеству. Алгоритм сначала сортирует ребра по их весу, а затем добавляет ребра в MST, начиная с минимального
Важно отметить, что алгоритм не добавляет ребра, образующие цикл. Алгоритм Крускала предпочтителен для разреженных графов
Алгоритм Прима также использует свойство жадности и идеально подходит для плотных графов. Основная идея MST Прима состоит в том, чтобы иметь два разных набора вершин; один набор содержит растущий MST, а другой – неиспользуемые вершины. На каждой итерации выбирается ребро минимального веса, которое соединяет эти два набора
Алгоритмы минимального охватывающего дерева необходимы для кластерного анализа, таксономии и широковещательных сетей
Эффективный программист хорошо владеет алгоритмами
Программисты постоянно учатся и развивают свои навыки, но есть несколько основных основ, которыми должен владеть каждый. Опытный программист знает различные алгоритмы, преимущества и недостатки каждого из них, а также то, какой алгоритм будет наиболее подходящим для того или иного сценария
Комментировать