Быстрый сортировка - это алгоритм сортировки, разработанный Тони Холлом. В среднем для сортировки n объектов требуется О ((nlogn) сравнение. В худшем случае требуется О ((n2) сравнение, но это нечасто. Фактически, быстрый сортировка обычно значительно быстрее других алгоритмов О ((nlogn), поскольку его внутренний цикл ("inner loop") может быть эффективно реализован на большинстве архитектур.
Быстрый сортировка использует стратегию "Divideandconquer" для разделения одной строки (списка) на две под-списки (под-списки).
Алгоритмные шаги:
1, выбирая из числа элемент, называемый пивотом,
2, переупорядочить числовые строки, все элементы, меньшие, чем базовые значения, помещены впереди, а все элементы, большие, чем базовые значения, помещены позади (одно и то же число может идти в любую сторону); после выхода из этого раздела, эта точка отсчета находится в середине строки. Это называется операцией разделения (partition).
3, рекурсивно (recursive) устраивает подстроки меньших элементов базового значения и больших элементов базового значения.
В самом низком случае рекурсионный алгоритм имеет числовые ряды размером 0 или 1, то есть он всегда был упорядочен. Хотя рекурсионный алгоритм всегда идет вниз, он всегда выходит, потому что в каждой итерации он перемещает по крайней мере один элемент в его последнее место.
Heapsort - это алгоритм сортировки, разработанный с использованием такой структуры данных. Склад - это структура, которая является почти полностью бинарным деревом, и в то же время удовлетворяет свойствам сбора: ключевое значение или индекс подноска всегда меньше (или больше) чем его родительский узел.
Средняя временная сложность укладки наряда - О ((nlogn) ⋅).
Алгоритмные шаги:
1, создание множества H [0...n-1]
2, заменить начало (max) и конец
3, уменьшить размер стока на 1 и вызвать shift_down ((0), чтобы привести данные на вершине новой матрицы в соответствующее положение
4, повторяем шаг 2 до тех пор, пока размер стола не достигнет 1.
Mergesort - эффективный алгоритм сортировки, основанный на операции с адсортировкой. Алгоритм является очень типичным применением метода разделения и завоевания.
Алгоритмные шаги:
1, заявка на пространство размером с сумму двух уже упорядоченных последовательностей, которое используется для хранения объединенных последовательностей
2, установка двух указателей, начальные позиции которых являются начальными позициями двух упорядоченных последовательностей
3, сравните элементы, на которые указывают два указателя, выберите относительно небольшие элементы, поместите их в объединительное пространство и переместите указатель в следующее место
4, повторяйте шаг 3 до тех пор, пока один из указателей не достигнет конца последовательности
5, прямо копирует все остальные элементы другой последовательности в конец объединенной последовательности
Алгоритм бинарного поиска - это алгоритм поиска определенного элемента в упорядоченном массиве. Процесс поиска начинается с среднего элемента массива, и если средний элемент именно тот, который нужно найти, то процесс поиска заканчивается; если определенный элемент больше или меньше среднего элемента, то поиск проводится в той половине массива, которая больше или меньше среднего элемента, и сравнивается, как и в начале, с среднего элемента.
БФПРТ решает классическую задачу выбора k-много (k-маленького) элемента из ряда n элементов, благодаря утонченному анализу BFPRT гарантирует, что в худшем случае сложность остается линейной. Идея алгоритма похожа на идею быстрого сортирования.
Алгоритмные шаги:
1, разделить n элементов на 5 групп, в группы n/5 (верхняя граница).
2, извлечение средних чисел каждой группы, любые способы сортировки, например, вставка сортировки.
3, рекурсивный алгоритм выбора вызова находит средние числа всех средних чисел в предыдущем шаге, установленные как x, и выбирает наименьшее из средних в случае даже нескольких средних чисел.
4, для деления матриц с помощью x, количество меньших и равных x определяется как k, а количество больших и равных x определяется как n - k.
5, если i==k, возвращает x; если i
Окончательное условие: при n=1 возвращается элемент i.
Алгоритм глубокого первоочередного поиска (англ. Deep-First-Search) - это алгоритм поиска, который проходит по узлам дерева глубоко вдоль дерева, прокладывая как можно глубже ветви дерева поиска. Когда все стороны v-го узла просматриваются, поиск возвращается к начальному узлу на стороне v-го обнаруженного узла. Процесс продолжается до тех пор, пока не найдены все узлы, доступные от исходного узла. Если не существует обнаруженного узла, выбирается один из них в качестве исходного узла и повторяется этот процесс.
Глубокий приоритетный поиск - классический алгоритм в диаграмме, использующий глубокий приоритетный поиск для получения соответствующей топологической последовательности для целевой диаграммы.
Подробное описание алгоритма:
1, доступ к вершине v;
2, последовательно с недоступных соседних точек v проходить глубокое первоочередное прохождение; до тех пор, пока не будут доступны вершины, которые совпадают с путями v;
3, если в данный момент в диаграмме остаются недоступные вершины, от недоступной вершины начинается повторное глубокое первоочередное прохождение до тех пор, пока все вершины в диаграмме не будут доступны.
Например: "Я не хочу, чтобы вы были похожи на меня, потому что я хочу быть похожим на вас".
После того, как DFS начнет с одной из вершин v в диаграмме доступа, DFS отправляется из v, посещает любую из ее соседних вершин w1; затем отправляется из w1, посещает вершины w2, которые соседствуют с w1, но еще не были посещены; затем отправляется из w2, делает аналогичные посещения,... и так далее, пока не достигается вершин u, которые были посещены всеми соседними вершинами.
Затем, сделав шаг назад, вернитесь к вершине, которую вы только что посетили в прошлый раз, и посмотрите, есть ли другие соседние вершины, которые не были посещены. Если есть, посетите эту вершину, а затем отправляйтесь с этой вершины и выполняйте похожий на предыдущий доступ; если нет, вернитесь к этому шагу и выполните поиск. Повторите процесс, пока не будут посещены все вершины в диаграмме.
Breadth-First-Search - это алгоритм графического поиска. Проще говоря, BFS - это расширение дерева по ширине дерева, начиная с корневых узлов. Если все узлы доступны, алгоритм прекращается.
Алгоритмные шаги:
1, сначала поместите корневой узел в очередь.
2, вытащить первый узел из очереди и проверить, является ли он целью.
Если цель найдена, поиск заканчивается и результаты возвращаются. В противном случае он добавляет в очередь все непосредственные подноски, которые еще не были проверены.
3, если строка пуста, значит, что весь график был проверен, и что в графике нет желаемой цели. Заканчивать поиск и возвращаться к сообщению о том, что цель не найдена.
4, повторяйте шаг 2.
Алгоритм Дикстра (англ. Dijkstra's Salgorithm) был предложен нидерландским компьютерным ученым Эйджером Дикстра. Алгоритм Дикстра использует широкий приоритетный поиск для решения задачи кратчайшего пути одноисточника неотъемлемого права на направленную диаграмму, в результате чего алгоритм получает дерево кратчайшего пути. Алгоритм часто используется в маршрутизационных алгоритмах или в качестве подмодуля других графических алгоритмов.
Введение в алгоритм включает в себя взвешенную линейную форму G, а также источник вершин S в G. Мы обозначаем V как совокупность всех вершин в G. Каждый край в графике представляет собой пару упорядоченных элементов, сформированных двумя вершинами. U, v обозначает, что от вершин u до v соединяются пути. Мы обозначаем E как совокупность всех сторон в G, а вес сторон определяется функцией взвешивания w: E→[0,∞].
Таким образом, w ((u, v) - это неотрицательный вес от вершины u до вершины v. Весы сторон можно представить как расстояние между двумя вершинами. Весы путей между двумя точками - это сумма веса всех сторон на этом пути. Известно, что в V есть вершины s и t, и алгоритм Dijkstra может найти наименьший вес пути от s до t.
Алгоритмные шаги:
1, значение расстояния между вершинами в T при S = {V0}, T = {остальные вершины}
В случае наличия
2, выберите из T вершину W с наименьшим расстоянием, которая не находится в S, и добавьте S
3, изменение значения расстояния вершин остальных T: изменение значения расстояния, если вставить W в качестве средней вершины и сократить значение расстояния от V0 до Vi
Повторите шаги 2, 3 и 3 до тех пор, пока S не содержит все вершины, то есть W = Vi.
Динамическое программирование - это метод, используемый в математике, компьютерной науке и экономике для решения сложных задач путем разделения исходных задач на относительно простые подзадачи. Динамическое программирование часто применяется к проблемам с накладной и наилучшими структурными свойствами, причем методы динамического программирования часто занимают гораздо меньше времени, чем примитивные решения.
Основная идея динамического планирования очень проста. В общем, для решения данной проблемы нам необходимо решить ее разные части ("подразделенные задачи") и реконструировать решения подзадач, чтобы получить решение первоначальной проблемы. Часто многие подзадачи очень похожи, поэтому методы динамического планирования пытаются решить каждую подзадачу только один раз, что уменьшает вычислительную нагрузку: как только решение данной подзадачи вычисляется, оно хранится в памяти, чтобы в следующий раз, когда потребуется решить ту же самую проблему, он был бы непосредственно проверен.
Самый классический вопрос о динамическом планировании относится к вопросу о рюкзаке.
Алгоритмные шаги:
1, наиболее оптимальные структурные свойства. Если решение, содержащееся в наиболее оптимальном решении проблемы, также является наиболее оптимальным, мы называем проблему наиболее оптимальной структурной свойством (т. е. она удовлетворяет принципам наибольшего оптимизации). Наиболее оптимальные структурные свойства дают важные подсказки для решения задачи алгоритмами динамического планирования.
2, накладность подпроблем. Накладность подпроблем означает, что при решении задачи сверху вниз с помощью рекурсивного алгоритма не всегда возникает новая проблема, и некоторые подпроблемы будут пересчитываться несколько раз. Алгоритм динамического планирования использует накладность этой подпроблемы, рассчитывая на каждую подпроблему только один раз, а затем сохраняет ее результаты в таблице, когда снова нужно рассчитать уже рассчитанную подпроблему, просто взгляните на результат в таблице, что дает более высокую эффективность.
Алгоритм простого Бейесовского классификации - это простой алгоритм классификации вероятности, основанный на теории Байеса. Основой классификации Байеса является вероятностное рассуждение, то есть то, как выполнить рассуждения и решения задач при наличии неопределенности различных условий, только зная о их вероятности. Вероятностное рассуждение соответствует рассуждению определенности.
Простые Бейесовские классификаторы, опирающиеся на точные модели естественной вероятности, дают очень хорошие классификационные результаты в группах образцов с контролируемым обучением. Во многих практических применениях параметры простых Бейесовских моделей оцениваются с помощью максимально-подобных оценок, т. е. простые Бейесы работают без использования вероятности Бейеса или любой модели Бейеса.
Несмотря на эти примитивные идеи и слишком упрощенные предположения, примитивный Бейесовский классификатор может работать довольно хорошо во многих сложных реалиях.