JavaScript 101

JavaScript logo
Популярные алгоритмы
Articulation points: Вершина в неориентированном связном графе является точкой сочленения (или вырезанной вершиной), если ее удаление (и проходящие через нее ребра) разъединяет граф. Точки сочленения представляют собой уязвимости в подключенной сети - единые точки, отказ которых разделил бы сеть на 2 или более отключенных компонента. Полезно для проектирования надежных сетей.

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

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

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

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

Floyd-Warshall: Алгоритм поиска кратчайших путей во взвешенном графе с положительными или отрицательными весами ребер (но без отрицательных циклов). Одно выполнение алгоритма найдет длины (суммарные веса) кратчайших путей между всеми парами вершин.

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

Prim: Алгоритм Прима - это жадный алгоритм, который находит минимальное охватывающее дерево для взвешенного неориентированного графа. Алгоритм работает, строя это дерево по одной вершине за раз, из произвольной начальной вершины, на каждом шаге добавляя самое дешевое возможное соединение из дерева в другую вершину.
Bubble sort: Сортировка пузырьков, иногда называемая сортировкой по убыванию, представляет собой простой алгоритм сортировки, который многократно проходит через список для сортировки, сравнивает каждую пару соседних элементов и меняет их местами, если они находятся в неправильном порядке (по возрастанию или по убыванию). Прохождение по списку повторяется до тех пор, пока не перестанут использоваться свопы, что указывает на то, что список отсортирован.

Counting sort: Подсчетная сортировка - это алгоритм сортировки коллекции объектов по ключам, которые являются небольшими целыми числами; то есть это целочисленный алгоритм сортировки. Он работает путем подсчета количества объектов, которые имеют каждое отдельное значение ключа, и использования арифметических операций с этими счетчиками для определения позиций каждого значения ключа в выходной последовательности. Время его работы линейно зависит от количества элементов и разницы между максимальным и минимальным значениями ключа, поэтому он подходит для прямого использования только в ситуациях, когда вариация ключей не намного превышает количество элементов. Однако он часто используется в качестве подпрограммы в другом алгоритме сортировки, Radix sort, который может более эффективно обрабатывать большие ключи.

Heap sort : Алгоритм сортировки, основанный на сравнении. Heapsort можно рассматривать как улучшенную сортировку выбора: как и этот алгоритм, он делит входные данные на отсортированную и несортированную области и итеративно сжимает несортированную область, извлекая самый большой элемент и перемещая его в отсортированную область. Улучшение состоит в использовании структуры данных кучи, а не поиска в линейном времени для поиска максимума.

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

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

Quick sort: Быстрая сортировка - это алгоритм «разделяй и властвуй». Быстрая сортировка сначала делит большой массив на два меньших подмассива: нижние элементы и высокие элементы. Затем Быстрая сортировка может рекурсивно сортировать подмассивы.

Radix sort: Это алгоритм сортировки несравнительных целых чисел, который сортирует данные с целочисленными ключами путем группировки ключей по отдельным цифрам, которые имеют одинаковую значащую позицию и значение. Позиционная нотация обязательна, но поскольку целые числа могут представлять строки символов (например, имена или даты) и специально отформатированные числа с плавающей запятой, сортировка по основанию не ограничивается целыми числами.

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

Shellsort: Шеллсорт, также известный как сортировка Шелла или метод Шелла, является сортировкой на месте сравнения. Это можно рассматривать как обобщение сортировки путем обмена (пузырьковая сортировка) или сортировки путем вставки (сортировка вставкой). Метод начинается с сортировки пар элементов на большом расстоянии друг от друга, а затем постепенного уменьшения разрыва между сравниваемыми элементами.
Hamming distance: Расстояние Хэмминга между двумя строками одинаковой длины - это количество позиций, в которых соответствующие символы различаются. Другими словами, он измеряет минимальное количество замен, необходимых для преобразования одной строки в другую, или минимальное количество ошибок, которые могли бы преобразовать одну строку в другую. В более общем контексте расстояние Хэмминга - это одна из нескольких строковых метрик для измерения расстояния редактирования между двумя последовательностями.

Knuth-Morris-Pratt: Алгоритм поиска строки Кнута – Морриса – Пратта ищет вхождения слова в текстовой строке используя наблюдение, что при возникновении несоответствия само слово содержит достаточно информации, чтобы определить, где следующее совпадение может начаться, минуя повторную проверку ранее сопоставленных символов.

Levenshtein distance: Расстояние Левенштейна - это строковая метрика для измерения разницы между двумя последовательностями. Неформально расстояние Левенштейна между двумя словами - это минимальное количество односимвольных правок (вставок, удалений или замен), необходимых для преобразования одного слова в другое.

Longest common substring: Находит самую длинную строку (или строки), которая является подстрокой (или являются подстроками) из двух или более строк. "Rabin-Karp" : "Алгоритм Карпа – Рабина - это алгоритм поиска строки, который использует хеширование для поиска любой из набора строк шаблонов в тексте.

Z-algorithm: Z-алгоритм находит вхождения слова в текстовой строке за линейное время.
Euclidean algorithm: Алгоритм Евклида - это эффективный метод вычисления наибольшего общего делителя двух чисел.

Horner method: Схема Горнера - алгоритм вычисления значения многочлена, записанного в виде суммы мономов (одночленов), при заданном значении переменной.

Binary search: Двоичный поиск, также известный как поиск с половинным интервалом, логарифмический поиск или двоичный поиск, представляет собой алгоритм поиска, который находит позицию целевого значения в отсортированном массиве.

Interpolation search: Поиск с интерполяцией - это алгоритм поиска ключа в массиве, который упорядочен по числовым значениям.

Jump search: Подобно двоичному поиску, поиск с переходом (или поиск по блоку) представляет собой алгоритм поиска отсортированных массивов. Основная идея состоит в том, чтобы проверять меньшее количество элементов (чем линейный поиск), перескакивая вперед на фиксированные шаги или пропуская некоторые элементы вместо поиска всех элементов.

Linear search: Линейный поиск или последовательный поиск - это метод поиска целевого значения в списке. Он последовательно проверяет каждый элемент списка на предмет целевого значения, пока не будет найдено совпадение или пока не будут найдены все элементы. Линейный поиск выполняется в худшем случае за линейное время и производит не более n сравнений, где n - длина списка.