Анализ алгоритмов (сложность)
Как алгоритмы проанализированы? Что заставляет quicksort иметь O(n^2) производительность худшего случая, в то время как сортировка слиянием имеет O(n log(n)) производительность худшего случая?
4 ответа
Это тема на весь семестр. В конечном итоге мы говорим о верхней границе количества операций, которые должны быть выполнены до завершения алгоритма, в зависимости от размера ввода. Мы не включаем коэффициенты (например, 10N против 4N ^ 2), потому что для достаточно большого N это больше не имеет значения.
Как доказать, что такое большой алгоритм, может быть довольно сложно. Для этого требуется формальное доказательство, и существует множество методов. Часто хороший специальный способ - просто подсчитать, сколько передач данных делает алгоритм. Например, если в вашем алгоритме есть вложенные циклы for, то для каждого из N элементов вы должны выполнить N раз. Обычно это O (N ^ 2).
Что касается сортировки слиянием, вы снова и снова разделяете данные пополам. Это занимает log2 (n). И для каждого разделения вы выполняете передачу данных, что дает N log (n).
быстрая сортировка немного сложнее, потому что в среднем случае это также n log (n). Вы должны представить, что произойдет, если ваш раздел разбивает данные так, что каждый раз вы получаете только один элемент на одной стороне раздела. Затем вам нужно будет разделить данные n раз вместо log (n) раз, что делает их N ^ 2. Преимущество быстрой сортировки заключается в том, что ее можно выполнить на месте, и мы обычно приближаемся к производительности N log (n).
Это вводный анализ материала курса алгоритмов.
Операция определяется (т. Е. Умножение), и анализ выполняется в терминах пространства или времени.
Эта операция считается с точки зрения пространства или времени. Обычно анализ выполняется, поскольку время является зависимой переменной от размера ввода.
Пример псевдокода:
foreach $elem in @list
op();
endfor
Будет выполнено n операций, где n - размер @list . Посчитайте сами, если вы мне не верите.
Для анализа быстрой сортировки и сортировки слиянием требуется приличный уровень математической сложности. Грубо говоря, вы решаете дискретное дифференциальное уравнение, полученное из рекурсивного отношения.
И quicksort , и merge sort разбивают массив на два, рекурсивно сортируют каждую часть, а затем объединяют результат. Быстрая сортировка разбивается, выбирая «стержневой» элемент и разбивая массив на меньшие или большие, чем стержень. Сортировка слиянием произвольно разбивает, а затем объединяет результаты за линейное время. В обоих случаях один шаг равен O (n), и если размер массива каждый раз уменьшается вдвое, это дает логарифмическое количество шагов. Таким образом, мы ожидаем O (n log (n)).
Однако быстрая сортировка имеет наихудший случай, когда разделение всегда неравномерно, поэтому вы получаете не количество шагов, пропорциональное логарифмическому значению n, а количество шагов, пропорциональное n. Сортировка слиянием разделяется ровно на две половины (или как можно ближе), поэтому у нее нет этой проблемы.
- Быстрая сортировка имеет много вариантов в зависимости от выбора точки поворота
- Предположим, мы всегда выбираем 1-й элемент в массиве как опорный
Если входной массив отсортирован, тогда быстрая сортировка будет только разновидностью сортировки по выбору! Потому что вы на самом деле не разделяете массив. . вы выбираете только первый элемент в каждом цикле
С другой стороны, сортировка слиянием всегда будет делить входной массив одинаковым образом, независимо от его содержимого!
Также обратите внимание: лучшая производительность в режиме «разделяй и властвуй», когда длина делений примерно равна!