Худшее, среднее и лучшее время работы алгоритма
Когда мы говорим, что время работы алгоритма равно $$T(n)$$, мы имеем в виду, что $$T(n)$$ является верхней границей времени выполнения, то есть имеет место для всех входных данных размера $$n$$. Это называется анализом наихудшего случая. Алгоритм может работать значительно быстрее на некоторых размерах входных данных $$n$$, но это не имеет значения при оценке худшего случая. Если на выполнение алгоритма требуется $$T(n) = cn^2+k$$ шагов хотя бы для одного входного значения $$n$$ и $$T(n) = cn+k$$ шагов на всех остальных входных данных, мы все равно говорим, что алгоритм является квадратным, то есть в худшем случае работает за время пропорциональное $$n^2$$. Нужно понимать, что знание сложности алгоритма в худшем случае является очень важным, так как имеет решающее значение в возможности применения данного алгорит
Популярная альтернатива анализу наихудшего случая — анализ среднего случая. Здесь мы не пытаемся найти худший случай времени выполнения, а попытаться вычислить ожидаемое время, затраченное на случайно выбранных входных данных. Такой анализ, как правило, сложнее, так как он включает в себя вероятностные рассуждения и часто требует знания о распределении входных данных. С другой стороны, он может быть более полезным, потому что иногда наихудший случай алгоритма является обманчиво плохим. Хорошим примером этого, является популярный алгоритм быстрой сортировки, время работы которого в худшем случае на массиве длины $$n$$ пропорциональное $$n^2$$, однако ожидаемое в среднем время работы пропорциональное $$n\log n$$.
Намного меньше информации об алгоритме может сказать оценка наилучшего случая.
 |
 |
|---|
Рассмотрим какую сложность в каждом из трех случаев имеет последовательный поиск элемента в массиве.
int LinearSearch(int[] arr, int x) < for (int i = 0; i < a.Length; i++) < if (arr[i] == x) return i; > return -1; > Худший случай
В худшем случае анализа, мы вычислим верхнюю границу времени работы алгоритма. Мы должны знать, случай, на котором выполняется максимальное количество выполняемых операций. Для линейного поиска, худшим случаем является поиск отсутсвующего в массиве элемента. В данном случае алгоритм сравнит каждый элемент массива с искомым элементом. Таким образом, в худшем случае временная сложность линейного поиска будет $$\Theta(n)$$, то есть алгоритм имеет линейный порядок, пропорциональный размеру входного массива.
Средний случай
При анализе сложности алгоритма в среднем случае, мы рассматриваем все возможные исходы входных данных и рассчитываем время вычисления для каждого из исходов. Для нахождения среднего значения поделим просто сумму на количество входов. Для анализа в среднем нам нужно знать распределение входных данных. Предположим, что в задаче линейного поиска все входные данные распределены равномерно (включая случай когда поиск осуществляется по отсутствующему элементу). Получаем среднюю сложность алгоритма
Лучший случай
При анализе сложности алгоритма в лучшем случае, мы вычисляем нижнюю границу времени работы алгоритма. Мы должны знать случай, на котором выполянется минимальное количество операций. В случае с линейным поиском, лучший случаем является поиск самого первого элемента в массиве. В таком случае количество затраченных операций будет всегда константным, то есть не будет зависеть от размера входного массива. Таким образом, сложность алгоритма линейного поиска в лучшем случае равна $$\Theta (1)$$.
В большинстве случаев, мы исследуем алгоритм на худшую оценку. В таком случае мы гарантируем, что время работы алгоритма не будет превосходить некоторого числа, что является хорошей информацией. Нахождение сложности алгоритма в среднем не является столь простой задачей, поскольку мы должны знать математическое распределение для всех возможных входных данных. Сложность алгоритма в лучшем случаем мало чем помогает при реальной оценке времени работы алгоритма. Таким образом алгоритм может в лучшем случае работать секунды, а в худшем случае дни и даже годы.
Для некоторых алгоритмов все три случая сложности совпадают. Например, сортировка слиянием в лучшем, среднем и худшем случае имеет сложность $$\Theta (n \log n)$$. Однако один из самых быстрых алгоритмов сортировки на практике — быстрая сортировка, имеет в худшем случае (массив уже отсортирован) квадратичную сложность работы, при выборе разделяющего элемента последним в массиве. Для сортировки вставками, наихудший случай достигается когда массив отсортирован в обратном порядке, а наилучший когда массив уже отсортирован в нужном порядке.
results matching » «
No results matching » «
Заметки быдлокодера
В Java 8, при попытке отсортировать массив элементов с помощью Arrays.sort, используются 2 основные оптимизированные сортировки: quick sort и merge sort. Первая выбирается для массивов из примитивов, а вторая в общем случае для любых объектов, для которых задан Comparator. Как гласит теория, оба алгоритма имеют одинаковую временную сложность O(n logn), но сортировка мержем гарантирует это, в то время как быстрая сортировка имеет такую оценку в среднем. Поэтому быстрая сортировка в java 8 сильно оптимизирована и включает в себя сразу 4 подхода, которые применяются в зависимости от характеристик массива. Над мерж-сортировкой так же достаточно сильно потрудились для оптимизации процесса мержа. Ниже приведены обобщенные описания идей, которые используются в обоих видах сортировок в Java8 и приведены иллюстрации улучшений алгоритмов по сравнению с классическими версиями. Само каноническое описание алгоритмов сортировок приводить не буду, т.к. предполагаю наличие этих знаний у читателя.
Merge Sort
Реализация сортировки расположена в java.util.TimSort и как гласит javadoc является адаптацией алгоритма мерж-сортировки Тима Питерса для питона. Его идея — продвинутая версия итеративного подхода сверху-вниз для мерж-сортировки.
Однако данный подход применяется не всегда. Когда размер массива небольшой, выгодней использовать сортировку вставками, что и делается, если размер массива меньше определенной константы (32 на момет написания статьи).
Бинарная сортировка вставками
Применяемая сортировка вставками так же оптимизирована. Ее идея состоит в том, чтобы использовать бинарный поиск в отсортированной части для того, чтобы обнаружить место, куда нужно вставить очередной элемент. После чего правая часть от этой позиции сдвигается вправо и на освободившееся место вставляется элемент.
Реализация merge sort
Если же массив больше порогового значения, то применяется собственно мерж-сортировка.
Для ее реализации используется идея нарезки массива на последовательности попеременно увеличивающихся и уменьшающихся последовательностей. Из этих последовательностей формируется массив возрастающих отрезков — для этого убывающие последовательности инвертируются. Таким образом каждый элемент массива — уже отсортированная часть исходного массива и остается только смержить между собой эти отрезки.
При этом, если длина отрезка слишком маленькая, то возрастающий отрезок формируется принудительно, получив очередную часть массива фиксированной длины и отсортировав ее с помощью все той же бинарной сортировки вставками.
Далее производится собственно процесс последовательного мержа отсортированных отрезков. При этом для оптимизации это производится не сразу, а при определенных условиях. До этого отрезки складываются в очередь и при разбалансировке условий производится мерж. Существенно это на принцип мержа не влияет, так что заострять внимание на этом не буду.
Во время мержа 2 отрезков на старте и при определенных условиях включается так называемый «галопирующий» проход. Его суть в том, чтобы пропустить элементы в левом или правом отрезках, которые соответственно заведомо меньше или больше наименьшего и наибольшего элементов в противоположном отрезке.
Quick sort
Быстрая сортировка в java 8 устроена достаточно запутанно. Она содержит в себе не только собственно быструю сортировку, но и сортировку вставками и merge-сортировку. В зависимости от условий выбирается наиболее подходящий к случаю вариант.
Сортировка содержится в классе java.util.DualPivotQuicksort.
Сортировка вставками
Как в случае с merge-сортировкой, при небольшом количестве элементов, выгодней использовать сортировку вставками. На момент написания статьи это 47 элементов.
Сама сортировка вставками делится на 2 варианта: левосторонняя и правосторонняя, в зависимости от того левую или правую часть массива относительно токена партицирования необходимо отсортировать.
Левосторонняя сортировка является традиционной реализацией алгоритма сортировки вставками без каких-либо улучшений.
Правосторонняя же использует 2 элемента для прохода влево на каждой итерации сортировки вставками, поэтому является более быстрой альтернативой традиционному методу.
Элементом a1 становится больший из 2 рабочих элементов. После выбора элементов производится поиск места вставки для a1. Затем продолжается поиск места для a2, начиная сразу за местом вставки a1. Таким образом экономится время на поиске места вставки.
Стандартное 3-way партицирование
Если же длина массива больше, чем порог сортировки вставками, но меньше чем определенный порог (286 элементов), то принудительно используется быстрая сортировка.
Как и в ситуации с сортировкой вставками, быстрая сортировка делится на 2 варианта: стандартное партицирование и двойное.
Под стандартным здесь понимается партицирование «голландский флаг», когда используется 1 токен, относительно которого производится партицирование на 3 части.
Двойное же подразумевает использование сразу 2 токенов и описание его будет приведено далее.
Используемый вариант определяется следующим образом. Длина массива делится примерно на 7 и выбираются 5 элементов массива относительно центра: 2 слева, 2 справа и центральный элемент. Эти элементы сортируются между собой в массиве. Если все они между собой различны, то используется двойное партицирование. Иначе, если есть хотя бы одна пара равных элементов, используется стандартное 3-way партицирование.
Стандартное партицирование является классической реализацией алгоритма — сортируемый массив разделяется на 3 части: меньше токена, равно токену и больше токена, а затем очередной обрабатываемый элемент массива перемещается в одну из этих частей.
Здесь k — очередной рабочий элемент, для которого необходимо решить, в какую часть его переместить.
После партицирования производится рекурсивная сортировка левой и правых частей. При этом для этих частей может использоваться сортировка вставками в зависимости от длины массива. И именно в этом месте для правой части используется правосторонний ее вариант.
Двойное партицирование
При двойном партицировании в качестве токенов выбираются элементы e2 и e4. Далее производится похожее на стандартное партицирование с той лишь разницей, что в центральной части складываются не равные одному токену элементы, а которые >= e2 и <= e4.
После партицирования проводится рекурсивная сортировка левой и правой частей (которые e4 соответственно) аналогично процессу стандартного партицирования. Для средней части дополнительно производится анализ — если она достаточно большая (> 4/7 массива), то производится перенос равных e2 и e4 элементов по соответствующим сторонам в отрезке.
После этого производится сортировка средней незатронутой части — либо всего отрезка от e2 к e4, если переноса не было, либо оставшейся части после переноса между равными элементами e2 и e4.
Merge sort
В случае, если длина массива больше порога применения быстрой сортировки (286 элементов), проверяются определенные условия на возможность применения merge-сортировки.
Для этого массив нарезают на возрастающие отрезки подобным образом, как в главе о merge-сортировке выше за исключением того, что не производится принудительная сортировка отрезка при малой длине. Если окажется, что в одном из отрезков присутствует больше определенного количества (33 на данных момент) одинаковых элементов или отрезков слишком много (больше 67), то производится переход к быстрой сортировке.
В противном случае начинается процесс последовательного мержа отрезков между собой. Он имеет гораздо более простой алгоритм, чем тот который используется в merge-сортировке выше и особо ничем не отличается от классического описания процесса мержа.
Поделиться
- Получить ссылку
- Электронная почта
- Другие приложения
Сортировки
Сортировкой (англ. sorting) называется процесс упорядочивания множества объектов по какому-либо признаку.
Так как данные могут хранится в разных структурах, то и алгоритмы для каждой структуры могут отличаться. Например, при хранении данных в списке сортировка кучей потребует $O(n^2 \log n)$ времени против $O(n \log n)$ с использованием массива; а вот сортировка пузырьком не изменится.
Также есть алгоритмы параллельной сортировки данных (т.н. Сортирующие сети), время работы которых в лучшем случае $O(\log n)$.
Классификация сортировок
Время работы
Эту классификацию обычно считают самой важной. Оценивают худшее время алгоритма, среднее и лучшее. Лучшее время — минимальное время работы алгоритма на каком-либо наборе, обычно этим набором является тривиальный $\big[ 1 \ldots n \big] $. Худшее время — наибольшее время. У большинства алгоритмов временные оценки бывают $O(n \log n)$ и $O(n^2)$.
Память
Параметр сортировки, показывающий, сколько дополнительной памяти требуется алгоритму. Сюда входят и дополнительный массив, и переменные, и затраты на стек вызовов. Обычно затраты бывают $O(1)$, $O(\log n)$, $O(n)$.
Устойчивость
Устойчивой сортировкой называется сортировка, не меняющая порядка объектов с одинаковыми ключами. Ключ — поле элемента, по которому мы производим сортировку.
Количество обменов
Количество обменов может быть важным параметром в случае, если объекты имеют большой размер. В таком случае при большом количестве обменов время алгоритма заметно увеличивается.
Детерминированность
Алгоритм сортировки называется детерминированным, если каждая операция присваивания, обмена и т.д. не зависит от предыдущих. Все сортирующие сети являются детерминированными.
Сравнение сортировок
Рассмотрим массив $\big[ 1 \ldots n \big]$. Для элементов должно выполняться отношение порядка.
| Название | Лучшее время | Среднее | Худшее | Память | Устойчивость | Обмены (в среднем) | Описание |
|---|---|---|---|---|---|---|---|
| Сортировка пузырьком (Bubble Sort) |
$O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Да | $O(n^2)$ | Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами. |
| Сортировка вставками (Insertion Sort) |
$O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Да | $O(n^2)$ | На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива до тех пор, пока весь набор входных данных не будет отсортирован. |
| Сортировка Шелла (Shellsort) |
$O(n\log^2)$ | Зависит от выбора шага | $O(n^2)$ | $O(1)$ | Нет | $O(n^2)$ | Является модификацией сортировки вставками, сортируем между собой элементы, стоящие на кратных нашему шагу местах. |
| Сортировка выбором (Selection Sort) |
$O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Нет | $O(n)$ | На $i$-ом шаге алгоритма находим минимальный среди последних $n — i + 1$, и меняем его местами с $i$-ым элементом в массиве. |
| Быстрая сортировка (Quick Sort) |
$O(n \log n)$ | $O(n \log n)$ | $O(n^2)$ (маловероятно) |
$O(\log n)$ (стек вызовов) |
Нет | $O(n \log n)$ | Один из самых известных и широко используемых алгоритмов сортировки. Алгоритм состоит в выборе опорного элемента, разделении массива на 2 части относительно опорного (одна — все элементы, меньшие опорного элемента, вторая — большие), и в сортировке полученных частей рекурсивным вызовом себя от них. |
| Сортировка слиянием (Merge Sort) |
$O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ (обычная реализация) $O(1)$ (модифицированная реализация) |
Да | $O(n \log n)$ | Алгоритм состоит в разделении массива пополам, сортировке половин и их слиянии. |
| Timsort | $O(n)$ | $O(n\log)$ | $O(n\log)$ | $O(n)$ | Да | $O(n\log)$ | Гибрид сортировки слиянием. Разбиваем массив на подмассивы фиксированной длины и сортируем каждый подмассив любой устойчивой сортировкой. После чего объединяем отсортированные подмассивы модифицированной сортировкой слиянием. |
| Сортировка кучей (Heap Sort) |
$O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(1)$ | Нет | $O(n \log n)$ | Строим из массива кучу, по очереди извлекаем минимум кучи. |
| Плавная сортировка (Smoothsort) |
$O(n)$ | $O(n\log)$ | $O(n\log)$ | $O(1)$ | Нет | $O(n\log)$ | Модификация сортировки кучей. Вместо двоичной кучи используем K-ую кучу Леонардо. |
| Терпеливая сортировка (Patience sorting) |
$O(n\log)$ | $O(n\log)$ | $O(n\log)$ | $O(n)$ | Нет | $O(n\log)$ | Раскидываем элементы массива по стопкам, после чего строим двоичную кучу из стопок. Позволяет также вычислить длину наибольшей возрастающей подпоследовательности данного массива. |
| Сортировка с помощью бинарного дерева (Tree Sort) |
$O(n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ | Да | $O(n)$ | Добавляем по очереди вершины в сбалансированное дерево поиска, проходим по всем вершинам в порядке возрастания. |
| Карманная сортировка (Bucket Sort) |
$O(n + k)$ | $O(n \log_k n)$ | $O(n \cdot k)$ | $O(n)$ | Да | — | Распределяем элементы в $k$ карманов, сортируем элементы внутри карманов, из каждого кармана данные записываются в массив в порядке разбиения. |
| Цифровая сортировка (Radix Sort) |
$O(n \lg n)$ | $O(n \lg n)$ | $O(n \lg n)$ | $O(n)$ | Да | — | Сортировка объектов равной длины, имеющих «разряды». обычно это строки или целые числа. Алгоритм состоит в том, чтобы отсортировать объекты по разрядам, начиная от младших к старшим. |
| Сортировка подсчетом (Counting Sort) |
$O(n)$ | $O(n + k)$ | $O(k)$ | $O(k)$ | Да | $O(n + k)$ | Сортировка целых чисел, входящих в какой-то небольшой диапазон. Создаем массив длины диапазона $k$, каждый элемент которого будет показывать, сколько исходных элементов равны данному. Бежим по массиву и считаем количество вхождений каждого числа. |
| Сортировка Хэна (Han’s Sort) |
$O(n \log \log n)$ | $O(n \log \log n)$ | $O(n \log \log n)$ | $O(n)$ | Да | $O(n \log \log n)$ | Очень сложная сортировка, основанная на принадлежности ключей к целым числам. Использует экспоненциальное поисковое дерево Андерсона. |
| Многопоточная сортировка слиянием (Multithreaded merge sort) |
$O(\frac>\log \frac>)$ | $O(\frac>\log \frac>)$ | $O(\frac>\log \frac>)$ | $O(n)$ | Да | $O(n \log n)$ | Отличается от сортировки слиянием только тем, что при рекурсивном вызове будет создавать новый поток. |
| PSRS-сортировка (PSRS-sorting) |
$O(\frac>\log \frac>)$ | $O(\frac>\log \frac>)$ | $O(\frac>\log \frac>)$ | $O(N_^2)$ | Нет | $O(n \log n)$ | Разделим массив на $N_$ подмассива и запустим в каждой быструю сортировку. После этого объединим все эти подмассивы. |
См. также
- Поисковые структуры данных
- Приоритетные очереди
- Поиск подстроки в строке
Источники информации
- Википедия — Алгоритмы сортировки
- Wikipedia —Sorting algorithm
- Хабрахабр — Бенчмарк алгоритмов сортировки
- Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 3-е изд. — М.: «Вильямс», 2013. — с. 174. — ISBN 978-5-8459-1794-2
- Дискретная математика и алгоритмы
- Сортировки
- Квадратичные сортировки
- Сортировки на сравнениях
- Многопоточные сортировки
- Другие сортировки
Последовательный поиск
Постановка задачи: пусть дан массив из N элементов. Необходимо определить номер элемента, который обладает определенными свойствами (чаще всего речь идет просто об элементе с определенным значением, равным k ), или установить что такого элемента в массиве нет.
Если массив является неупорядоченным, то единственный алгоритм поиска, применимый в этом случае – последовательный. Суть метода – последовательно перебираются все элементы массива, если на каком-то шаге цикла обнаруживается, что массив закончился или обнаруживается искомый элемент, то цикл заканчивается.
Пример фрагмента программы
a : array[1..N] of integer;