Анализ алгоритмов (сложность)

Question

Как анализируются алгоритмы? Что дает быстрой сортировке O(n^2) производительность в худшем случае, а сортировка слиянием - O(n log(n)) производительность в худшем случае?

Answer 1

Это тема для всего семестра. В конечном итоге мы говорим о верхней границе числа операций, которые должны быть выполнены до завершения алгоритма, в зависимости от размера ввода. Мы не включаем коэффициенты (т.е. 10N против 4N ^ 2), потому что для достаточно большого N это уже не имеет значения.

Как доказать, что такое большой алгоритм, может быть довольно сложно. Это требует формального доказательства и существует множество методов. Часто хороший способ adhoc состоит в том, чтобы просто посчитать, сколько проходов данных делает алгоритм. Например, если ваш алгоритм вложен в циклы, то для каждого из N элементов вы должны работать N раз. Как правило, это будет O (N ^ 2).

Что касается сортировки слиянием, вы делите данные пополам снова и снова. Это занимает log2 (n). И для каждого разделения вы делаете передачу данных, которая дает N log (n).

Быстрая сортировка немного сложнее, потому что в среднем случае это также n log (n). Вы должны представить, что произойдет, если ваш раздел разбивает данные таким образом, что каждый раз, когда вы получаете только один элемент на одной стороне раздела. Тогда вам нужно будет разделить данные n раз вместо log (n) раз, что делает их N ^ 2. Преимущество быстрой сортировки состоит в том, что это можно сделать на месте, и мы обычно приближаемся к производительности N log (n).

Answer 2

1. Это вводный анализ алгоритмов материалов курса.

2. Определяется операция (т. Е. Умножение), и анализ выполняется с точки зрения пространства или времени.

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

Пример псевдокода:

foreach $elem in @list

   op();

endfor

Будет выполнено n операций, где n - размер @list. Считай это сам, если не веришь мне.

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

Answer 3

Обе быстрая сортировка и сортировка слиянием разбивают массив на две части, рекурсивно сортируют каждую часть, а затем объединяют результат. Quicksort разделяется, выбирая элемент «pivot» и разбивая массив на меньшие или большие, чем «pivot». Сортировка слиянием разделяется произвольно, а затем объединяет результаты в линейное время. В обоих случаях одним шагом является O (n), и если размер массива уменьшается вдвое, это дает логарифмическое количество шагов. Таким образом, мы ожидали бы O (n log (n)).

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

Answer 4

• У быстрой сортировки есть много вариантов в зависимости от выбора оси вращения
• Давайте предположим, что мы всегда выбираем 1-й элемент в массиве как опорный пункт

Если входной массив отсортирован, то Быстрая сортировка будет только разновидностью сортировки выбора! Потому что вы на самом деле не делите массив ... вы выбираете только первый элемент в каждом цикле

С другой стороны, сортировка слиянием всегда будет делить входной массив одинаковым образом, независимо от его содержимого!

Также обратите внимание: лучшая производительность в разделяй и властвуй, когда длина делений почти равна!