7 алгоритмов, которые должен знать каждый программист

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

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

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

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

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

Алгоритм обычно реализуется с помощью набора. Алгоритм Дейкстры очень эффективен при реализации с Min Heap; вы можете найти кратчайший путь всего за O (V + ElogV) времени (V - количество вершин, а E - количество ребер в данном графе).

У алгоритма Дейкстры есть свои ограничения; он работает только с ориентированными и неориентированными графами с ребрами положительного веса. Для отрицательных весов обычно предпочтительнее алгоритм Беллмана-Форда.

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

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

У нас есть пара алгоритмов сортировки в этом списке, и сортировка слиянием является одним из наиболее важных алгоритмов. Это эффективный алгоритм сортировки, основанный на методе программирования «Разделяй и властвуй». В худшем случае сортировка слиянием может отсортировать «n» чисел всего за O (nlogn) времени. По сравнению с примитивными методами сортировки, такими как Пузырьковая сортировка (это занимает время O (n ^ 2)), сортировка слиянием очень эффективна.

Связанный: Введение в алгоритм сортировки слиянием

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

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

Quicksort - это еще один алгоритм сортировки, основанный на методе программирования Divide and Conquer. В этом алгоритме сначала выбирается элемент в качестве стержня, а затем весь массив разбивается вокруг этого стержня.

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

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

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

4. Поиск в глубину

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

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

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

5. Поиск в ширину

Поиск в ширину (BFS) также известен как обход порядка уровней для деревьев. BFS работает в O (V + E) аналогично алгоритму DFS. Однако BFS использует очередь вместо стека. DFS погружается в график, тогда как BFS проходит по графику вширь.

Алгоритм BFS использует очередь для отслеживания вершин. Непосещенные соседние вершины посещаются, помечаются и помещаются в очередь. Если вершина не имеет смежных вершин, то вершина удаляется из очереди и исследуется.

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

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

Бинарный поиск - это простой алгоритм поиска необходимого элемента в отсортированном массиве. Он работает путем многократного деления массива пополам. Если требуемый элемент меньше самого среднего элемента, то левая часть среднего элемента обрабатывается дальше; в противном случае правая сторона делится пополам и снова ищется. Процесс повторяется до тех пор, пока не будет найден требуемый элемент.

Наихудшая временная сложность двоичного поиска составляет O (logn), что делает его очень эффективным при поиске по линейным массивам.

7. Минимальные алгоритмы связующего дерева

Минимальное остовное дерево (MST) графа имеет минимальную стоимость среди всех возможных остовных деревьев. Стоимость остовного дерева зависит от веса его ребер. Важно отметить, что может быть более одного минимального связующего дерева. Существует два основных алгоритма MST, а именно Kruskal’s и Prim.

Алгоритм Краскала создает MST, добавляя край с минимальными затратами к растущему набору. Алгоритм сначала сортирует ребра по их весу, а затем добавляет ребра в MST, начиная с минимума.

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

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

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

Эффективный программист хорошо разбирается в алгоритмах

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

Введение в алгоритм сортировки оболочки

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

Читать далее

Об авторе