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

• ### Алгоритм I: алгоритм быстрого сортировки

Быстрая сортировка - это алгоритм сортировки, разработанный Тони Холлом. В среднем для сортировки n объектов требуется n (n) сравнений. В худшем случае требуется n (n) сравнений, но это нечасто встречается. Фактически, быстрая сортировка обычно значительно быстрее других алгоритмов, поскольку ее внутренний цикл (innerloop) может быть эффективно реализован на большинстве архитектур.

Быстрая сортировка использует тактику разделения и завоевания (Divideandconquer) для разделения последовательного списка на два под-списка.

Шаги алгоритма:

• 1, выберите элемент из ряда, называемый базовым элементом (пивотом),

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

• 3., рекурсивное (recursive) подсоединение подмножеств, меньших, чем элементы базового значения, и подмножеств, больших, чем элементы базового значения.

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

• ### Алгоритм 2: Алгоритм сортировки кучи

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

Средняя временная сложность сортировки стека составляет O ((nlogn) 。

Шаги алгоритма:

• 1. Создание кучи H[0..n-1]

• 2, переключайте начало (максимальное значение) и конец.

• 3, уменьшить размер стека до 1 и вызвать shift_down ((0)), чтобы переместить новую вершину массива в соответствующее положение

• 4, повторяем шаг 2, пока размер кучи 1

• Третий алгоритм: репатриация и сортировка

Mergesort - эффективный алгоритм сортировки, основанный на операции по объединению. Этот алгоритм является типичным примером применения метода деления и завоевания.

Шаги алгоритма:

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

• 2, устанавливает два указателя, начальные позиции которых являются начальными позициями двух уже сортированных последовательностей

• Сравнение элементов, на которые указывают два указателя, выбор относительно небольшого элемента, помещенного в объединяющее пространство, и перемещение указателя в следующее положение

• 4, повторяйте шаг 3 до тех пор, пока один из указателей не достигнет конца последовательности

• 1. копирование всех оставшихся элементов другой последовательности прямо в конец последовательности объединения

• Алгоритм 4: алгоритм двойного поиска

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

• ### Алгоритм пятый: BFPRT ((Линейный поисковый алгоритм))

Проблема, которую решает алгоритм BFPRT, является классической: из некоторой последовательности из n элементов выбирается k-й элемент (k-й элемент), который с помощью хитрого анализа может гарантировать линейную временную сложность в худшем случае. Идея алгоритма похожа на идею быстрого сортировки, и, конечно же, для того, чтобы алгоритм в худшем случае мог достичь временной сложности o (n), пять авторов алгоритма сделали тонкую обработку.

Шаги алгоритма:

• 1, разделяем n элементов на группы по 5 в каждой из n/5 (верхней границы).

• 1. Выбрать среднее число каждой группы, произвольный способ сортировки, например, вставка сортировки

• 3, алгоритм рекурсивного вызова selection находит среднее число всех средних чисел, представленных в предыдущем шаге, и задает его на x, выбирая наименьшее из числа средних чисел в случае, если их количество является нечетным.

• 4, используйте x для разделения массива, если число меньше, чем равное x, равно k, число больше, чем x, равно n-k.

• 5, если i==k, возвращает x; если ik, рекурсивно ищет элемент меньше i-k из элементов больше x.

  Окончательное условие: когда n = 1, возвращается i элемент.

• Алгоритм 6: DFS ((глубокий приоритетный поиск))

Deep-First-Search (DFS) - поисковый алгоритм, проходящий по глубине дерева вдоль узлов дерева, чтобы найти как можно более глубокие ветви дерева. Когда все стороны узла v уже исследовались, поиск возвращается к начальному узлу на той стороне, где был обнаружен узел v. Этот процесс продолжается до тех пор, пока не будут найдены все узлы, доступные от узла источника. Если есть еще не найденные узлы, выбирается один из них в качестве узла источника и повторяется вышеуказанный процесс, весь процесс повторяется до тех пор, пока все узлы не будут посещены.

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

Внимательно ознакомьтесь со следующими алгоритмами:

• 1 , посещение вершины v;

• 2 - начать с не посещенных соседних точек v, и сделать первоочередное глубокое прохождение по диаграмме, до тех пор, пока в диаграмме не будут посещены вершины, которые имеют путь, совпадающий с v;

• 1. Если на данный момент на карте есть вершины, которые еще не были посещены, начинать с одной из не посещенных вершин и переходить по глубокому приоритету, пока все вершины на карте не будут посещены.

  Приведем пример, который может показаться абстрактным:

  DFS начинает с вершины v в диаграмме доступа, отправляется от v и посещает любую из ее соседних вершин w1; затем отправляется от w1 и посещает вершины, которые соседствуют с w1, но еще не посещены w2; затем отправляется от w2 и совершает аналогичный доступ,… так продолжается до тех пор, пока не достигнет вершины u, на которой были посещены все соседствующие вершины.

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

• Алгоритм 7: BFS (Broad Foresight Prioritized Search)

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

Шаги алгоритма:

• 1. Во-первых, введите корневой узел в строку.
• 1. Выберите первый узел из очереди и проверьте, является ли он целью.

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

• 3 , Если строка пустая, значит, что вся карта была проверена, т.е. на карте нет желаемой цели. Завершить поиск и вернуться к сообщению, что цель не найдена.

• 4, повторяем шаг 2.

• Алгоритм 8: Алгоритм Дикстры

Алгоритм Дикстры (англ. Dijkstra’s salt algorithm) был предложен голландским компьютерным ученым Ицхером Дикстром. Алгоритм Дикстора использует приоритетное поиск широты для решения задачи кратчайших путей из одного источника для неотрицательных графов. В результате алгоритм получает древо кратчайших путей.

Ввод алгоритма включает в себя весомый направленный график G, а также источник в G с вершиной S. Мы используем V, чтобы обозначить совокупность всех вершин в G. Стороны в каждом графике представляют собой пары упорядоченных элементов, образованных двумя вершинами.[0,∞] определение ≠

Таким образом, w(u,v) - это неотрицательный вес (((weight) от вершины u до вершины v. Вес стороны можно представить как расстояние между двумя вершинами. Вес пути между двумя точками - это сумма весов всех сторон на этом пути. Известно, что в V есть вершины s и t, а алгоритм Dijkstra может найти наименьший весной путь от s до t (например, кратчайший путь).

Шаги алгоритма:

• 1, начальное время S = {V0}, T = {остальные вершины}, значение расстояния от вершины в T Если существует , d ((V0,Vi) является значением на дуге Если не существует , d (V0,Vi) равен∞

• 2, выберите из T вершину W с наименьшим расстоянием и не входящую в S, и присоедините ее к S

• 3., Изменить значение расстояния от вершины в остальном T: если добавить W в качестве средней вершины, то значение расстояния от V0 до Vi будет укорочено, и это значение расстояния будет изменено

  Повторите вышеприведенные шаги 2 и 3 до тех пор, пока S не содержит все вершины, то есть W=Vi

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

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

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

Самый классический вопрос о динамическом планировании относится к вопросу о рюкзаке.

Шаги алгоритма:

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

2 ‒ Складённость подзадач ‒ подзадач не всегда являются новыми, а некоторые подзадачи рассчитываются несколько раз. При использовании рекурсивных алгоритмов для решения задач сверху вниз, подзадачи не всегда являются новыми, а некоторые из них рассчитываются несколько раз.

• ### Алгоритм 10: примитивный классификационный алгоритм Байеса

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

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

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