Алгоритм 1: Алгоритм быстрой сортировки
Quicksort — это алгоритм сортировки, разработанный Тони Холлом. В среднем для сортировки n элементов требуется Ο(n log n) сравнений. В худшем случае требуется O(n2) сравнений, но это встречается не часто. На самом деле быстрая сортировка обычно значительно быстрее других алгоритмов O(n log n), потому что ее внутренний цикл может быть эффективно реализован на большинстве архитектур.
Быстрая сортировка использует стратегию «разделяй и властвуй», чтобы разделить список на два подсписка.
Шаги алгоритма:
1 Выберите элемент из последовательности, называемый «стержнем»,
2 Измените порядок последовательности: все элементы, меньшие эталонного значения, помещаются перед эталонным значением, а все элементы, превышающие эталонное значение, размещаются за эталоном (одинаковое число может идти с любой стороны). После выхода из раздела эталон находится в середине последовательности. Это называется операцией разделения.
3 Рекурсивно отсортируйте подмассивы элементов меньше эталонного значения и подмассивы элементов больше эталонного значения.
В нижнем случае рекурсии размер последовательности равен нулю или единице, которая всегда сортируется. Хотя он продолжает повторяться, алгоритм всегда будет завершаться, потому что на каждой итерации он будет помещать по крайней мере один элемент в его последнюю позицию.
Подробное введение:быстрая сортировка
Алгоритм 2: Алгоритм сортировки кучей
Heapsort (Heapsort) относится к алгоритму сортировки, разработанному с использованием структуры данных кучи. Стекирование — это структура, которая аппроксимирует полное бинарное дерево и в то же время удовлетворяет свойству стекирования: то есть значение ключа или индекс дочернего узла всегда меньше (или больше) его родительского узла.
Средняя временная сложность сортировки кучей равна Ο(nlogn).
Шаги алгоритма:
- Создайте кучу H[0..n-1]
- Поменять местами голову кучи (максимальное значение) и хвост кучи
3. Уменьшите размер кучи на 1 и вызовите shift_down(0), цель состоит в том, чтобы настроить верхние данные нового массива на соответствующую позицию.
4. Повторяйте шаг 2, пока размер кучи не станет равным 1.
Подробное введение:сортировка кучей
Алгоритм 3: сортировка слиянием
Сортировка слиянием (Merge sort, тайваньский перевод: сортировка слиянием) — это эффективный алгоритм сортировки, основанный на операции слияния. Этот алгоритм является очень типичным применением принципа «разделяй и властвуй».
Шаги алгоритма:
1. Подать заявку на пространство, чтобы размер был суммой двух отсортированных последовательностей, и это пространство использовалось для хранения объединенной последовательности.
2. Установите два указателя, начальные позиции являются начальными позициями двух отсортированных последовательностей.
3. Сравните элементы, на которые указывают два указателя, выберите относительно небольшой элемент для помещения в пространство слияния и переместите указатель в следующую позицию.
4. Повторяйте шаг 3, пока указатель не достигнет конца последовательности.
5. Скопируйте все оставшиеся элементы другой последовательности непосредственно в конец объединенной последовательности.
Подробное введение:Сортировка слиянием
Алгоритм 4: Алгоритм бинарного поиска
Алгоритм бинарного поиска — это алгоритм поиска, который находит определенный элемент в упорядоченном массиве. Процесс поиска начинается со среднего элемента массива.Если средний элемент является именно тем элементом, который нужно найти, процесс поиска заканчивается, если конкретный элемент больше или меньше среднего элемента, он ищет в половине массива. массив, который больше или меньше среднего элемента. , и начинаем сравнение со среднего элемента, как в начале. Если на каком-то шаге массив пуст, значит, он не может быть найден. Этот алгоритм поиска уменьшает диапазон поиска наполовину для каждого сравнения. Половинный поиск каждый раз уменьшает область поиска вдвое, а временная сложность равна Ο(logn).
Подробное введение:алгоритм бинарного поиска
Алгоритм 5: BFPRT (алгоритм линейного поиска)
Проблема, решаемая алгоритмом BFPRT, очень классическая, то есть k-й наибольший (k-й наименьший) элемент выбирается из последовательности элементов n. Благодаря умному анализу BFPRT может гарантировать, что наихудший случай по-прежнему будет линейной временной сложностью. Идея этого алгоритма аналогична идее быстрой сортировки.Конечно, для того, чтобы алгоритм по-прежнему достиг временной сложности O (n) в худшем случае, пять авторов алгоритма выполнили деликатную обработку .
Шаги алгоритма:
1. N элементы каждой группы 5, делится на N / 5 (верхняя связанная) группа.
2. Возьмите медиану каждой группы и используйте любой метод сортировки, например сортировку вставками.
3. Рекурсивно вызовите алгоритм выбора, чтобы найти медиану всех медиан на предыдущем шаге, установите ее как x и установите ее для выбора меньшей в середине в случае четного числа медиан.
4. Используйте x для разделения массива, установите число меньше или равное x как k, а число больше x как n-k.
5. Если i==k, вернуть x, если i
Условие завершения: когда n=1, возвращаемый элемент равен i.
Подробное введение:Алгоритм корреляции линейного поиска
Алгоритм 6: DFS (поиск в глубину)
Поиск в глубину — это своего рода поисковый алгоритм. Он обходит узлы дерева по глубине дерева, ища ветви дерева как можно глубже. Когда все ребра узла v будут исследованы, поиск вернется к начальному узлу того ребра, которое нашло узел v. Этот процесс продолжается до тех пор, пока не будут обнаружены все узлы, доступные из исходного узла. Если все еще есть необнаруженные узлы, выберите один из них в качестве исходного узла и повторите описанный выше процесс Весь процесс повторяется до тех пор, пока не будут посещены все узлы. DFS — это слепой поиск.
Поиск в глубину — это классический алгоритм теории графов. С помощью алгоритма поиска в глубину можно создать соответствующую таблицу топологической сортировки целевого графа. Использование таблицы топологической сортировки позволяет легко решить многие связанные задачи теории графов, такие как проблема максимального пути и так далее. Структура данных кучи обычно используется для помощи в реализации алгоритма DFS.
Шаги алгоритма обхода графа в глубину:
1. Посетить вершину v;
2. Начиная с непосещенных соседних точек v по очереди, выполнять обход в глубину графа до тех пор, пока не будут посещены вершины графа, имеющие путь с v;
3. Если в этот момент в графе еще остались непосещенные вершины, начиная с непосещенной вершины, снова выполняется обход в глубину до тех пор, пока не будут посещены все вершины графа.
Приведенное выше описание может быть абстрактным, например:
После того, как DFS посещает некоторую начальную вершину v в графе, она начинает с v и посещает любую соседнюю с ней вершину w1, затем начинает с w1, посещает вершину w2, смежную с w1, но еще не посещенную, и затем начинает с w2, Выполняются аналогичные посещения, ... и так далее, пока не будет достигнута вершина u, в которой были посещены все соседние вершины.
Затем сделайте шаг назад к вершине, которая была только что посещена, чтобы увидеть, есть ли другие смежные вершины, которые не были посещены. Если есть, посетить эту вершину, а затем перейти из этой вершины, чтобы выполнить посещение, аналогичное предыдущему; если нет, вернуться на один шаг назад для поиска. Повторяйте описанный выше процесс, пока не будут посещены все вершины связного графа.
Подробное введение:поиск в глубину
Алгоритм 7: BFS (поиск в ширину)
Поиск в ширину — это алгоритм поиска по графу. Проще говоря, BFS начинается с корневого узла и проходит узлы дерева (графа) по ширине дерева (графа). Если все узлы посещены, алгоритм прерывается. BFS также является слепым поиском. Структура данных очереди обычно используется для помощи в реализации алгоритма BFS.
Шаги алгоритма:
1. Сначала поместите корневой узел в очередь.
2. Возьмите первый узел из очереди и проверьте, является ли он целевым.
- Если цель найдена, завершить поиск и вернуть результат.
- В противном случае добавьте в очередь все его непроверенные прямые дочерние элементы.
3. Если очередь пуста, это означает, что было проверено все изображение, т. е. в образе нет объекта для поиска. Завершите поиск и верните «цель не найдена».
4. Повторите шаг 2.
Подробное введение:Поиск в ширину
Алгоритм 8: Алгоритм Дейкстры
Алгоритм Дейкстры был предложен голландским ученым-компьютерщиком Эжером Дейкстрой. Алгоритм Дейкстры использует поиск в ширину для решения задачи поиска кратчайшего пути с одним источником для ориентированных графов с неотрицательным весом, и алгоритм, наконец, получает дерево кратчайших путей. Этот алгоритм часто используется в алгоритмах маршрутизации или как подмодуль других графовых алгоритмов.
Входные данные алгоритма состоят из взвешенного ориентированного графа G и исходной вершины S в G. Обозначим множество всех вершин в G через V. Каждое ребро в графе представляет собой упорядоченную пару элементов, образованную двумя вершинами. (u, v) означает, что существует путь из вершины u в v. Обозначим множество всех ребер в G через E, а веса ребер определяются весовой функцией w: E → [0, ∞]. Следовательно, w(u, v) — неотрицательный вес от вершины u до вершины v. Вес ребра можно рассматривать как расстояние между двумя вершинами. Вес пути между любыми двумя точками равен сумме весов всех ребер пути. Учитывая, что в V есть вершины s и t, алгоритм Дейкстры может найти путь с наименьшим весом (например, кратчайший путь) из s в t. Этот алгоритм также может найти кратчайший путь из вершины s в любую другую вершину графа. Для ориентированных графов без отрицательных весов алгоритм Дейкстры является самым быстрым из известных в настоящее время алгоритмов поиска кратчайшего пути с одним источником.
Шаги алгоритма:
1. Начальное время S={V0}, T={оставшиеся вершины}, значение расстояния, соответствующее вершинам в T
Если есть
Если
2. Выберите вершину W с наименьшим значением расстояния от T, а не от S, и добавьте S
3. Измените значение расстояния вершин в оставшейся T: если W добавляется в качестве промежуточной вершины, значение расстояния от V0 до Vi укорачивается, затем измените значение расстояния
Повторяйте вышеуказанные шаги 2 и 3 до тех пор, пока все вершины не будут включены в S, то есть W=Vi
подробно:Алгоритм Дейкстры
Алгоритм 9: Алгоритм динамического программирования
Динамическое программирование — это метод, используемый в математике, информатике и экономике для решения сложных задач путем разбиения исходной задачи на относительно простые подзадачи. Динамическое программирование часто подходит для задач с перекрывающимися подзадачами и оптимальными свойствами подструктуры, а затраты времени на методы динамического программирования часто намного меньше, чем на наивные решения.
Основная идея динамического программирования очень проста. Грубо говоря, чтобы решить данную проблему, нам нужно решить ее разные части (то есть подзадачи), а затем объединить решения подзадач, чтобы получить решение исходной проблемы. Часто многие подзадачи очень похожи, по этой причине динамическое программирование пытается решить каждую подзадачу только один раз, тем самым уменьшая объем вычислений: как только решение данной подзадачи решено, оно запоминается, чтобы в следующий раз нужна та же подзадача. Проверяйте таблицу непосредственно при решении. Эта практика особенно полезна, когда количество повторяющихся подзадач растет экспоненциально с размером входных данных.
Самая классическая задача динамического программирования — задача о рюкзаке.
Шаги алгоритма:
1. Оптимальные свойства подструктуры. Если решение подзадач, содержащихся в оптимальном решении задачи, также оптимально, то говорят, что задача обладает свойством оптимальной подструктуры (т. е. удовлетворяет принципу оптимизации). Оптимальные свойства подструктуры дают важные подсказки алгоритмам динамического программирования для решения задач.
2. Перекрывающийся характер подзадач. Свойство перекрытия подзадач означает, что при решении задачи сверху вниз рекурсивным алгоритмом генерируемые каждый раз подзадачи не всегда являются новыми задачами, а некоторые подзадачи будут многократно повторяться. Алгоритм динамического программирования использует перекрывающийся характер этой подзадачи.Он вычисляет каждую подзадачу только один раз, а затем сохраняет результаты вычислений в таблице.Когда вычисленная подзадача должна быть вычислена снова, это только в таблице Просто посмотрите на результаты, чтобы получить высокую эффективность.
Подробная ссылка:
От глобальной навигации к методу ввода: поговорим о динамическом программировании
Алгоритм 10: Алгоритм наивной байесовской классификации
Алгоритм наивной байесовской классификации представляет собой простой алгоритм вероятностной классификации, основанный на теореме Байеса. В основе байесовской классификации лежат вероятностные рассуждения, то есть способы решения задач рассуждений и принятия решений, когда существование различных условий является неопределенным и известна только вероятность их возникновения. Вероятностные рассуждения противоположны детерминистическим рассуждениям. Наивный байесовский классификатор основан на предположении о независимости, то есть предполагается, что каждый признак выборки не связан с другими признаками.
Наивный байесовский классификатор опирается на точную модель естественной вероятности и может получить очень хорошие результаты классификации в наборе выборок с учителем. Во многих практических приложениях параметры наивной байесовской модели оцениваются с использованием метода оценки максимального правдоподобия, другими словами, наивная байесовская модель работает без использования байесовской вероятности или какой-либо байесовской модели.
Несмотря на эти наивные идеи и чрезмерно упрощенные предположения, наивные байесовские классификаторы все еще могут достигать неплохих результатов во многих сложных реальных ситуациях.
Подробная ссылка: