Когда алгоритм quicksort принимает O (n ^ 2) время?
Quicksort худшее состояние
Ответ 1
Quicksort работает, беря шарнир, затем помещая все элементы ниже этого шарнира с одной стороны и все более высокие элементы с другой; Затем он рекурсивно сортирует две подгруппы одинаковым образом (все время до тех пор, пока все не будет отсортировано.) Теперь, если вы выбираете наихудший стержень каждый раз (самый высокий или самый низкий элемент в списке), у вас будет только одна группа для сортировать со всем в этой группе, кроме оригинального центра, который вы выбрали. По сути, это дает вам n групп, каждая из которых должна быть повторена n раз, следовательно, сложность O (n ^ 2).
Наиболее распространенной причиной этого является то, что стержень выбран первым или последним элементом в списке в реализации быстрой сортировки. Для несортированных списков это так же верно, как и для любых других, однако для отсортированных или почти отсортированных списков (которые встречаются довольно часто на практике) это, скорее всего, даст вам сценарий наихудшего случая. Вот почему все полуприличные реализации имеют тенденцию брать центр от центра списка.
Существуют модификации стандартного алгоритма быстрой сортировки, чтобы избежать этого крайнего случая - один из примеров - двойная круговая сортировка, которая была интегрирована в Java 7.
Ответ 2
Короче говоря, Quicksort для сортировки низшего элемента массива сначала работает так:
- Выберите элемент поворота
- Массив предварительной сортировки, так что все элементы, меньшие, чем сводная, находятся на левой стороне
- Рекурсивно выполните шаги 1. и 2. для левой и правой сторон
В идеале вы хотели бы иметь элемент pivot, который разделяет последовательность на две одинаково длинные подпоследовательности, но это не так просто.
Существуют разные схемы выбора элемента поворота. Ранние версии просто заняли самый левый элемент. В худшем случае элемент разворота всегда будет самым низким элементом текущего диапазона.
Самый левый элемент - это точка поворота
В этом случае легко понять, что наихудший случай - это монотонный растущий массив:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Самый правый элемент - это шарнир
Аналогично, при выборе самого правого элемента наихудшим случаем будет убывающая последовательность.
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
Центральный элемент - это стержень
Одним из возможных решений для наихудшего случая для предварительно отсортированных массивов является использование центрального элемента (или немного левее центра, если последовательность имеет четную длину). Тогда худший случай будет довольно экзотическим. Его можно построить, изменив алгоритм быстрой сортировки, чтобы установить элементы массива, соответствующие выбранному в данный момент элементу поворота, в монотонное возрастающее значение. То есть мы знаем, что первая ось является центром, поэтому центр должен иметь наименьшее значение, например 0. Затем он поменяется на крайний левый, то есть крайнее левое значение теперь находится в центре и будет следующим элементом поворота, поэтому оно должно быть 1. Теперь мы уже можем догадаться, что массив будет выглядеть следующим образом:
1 ? ? 0 ? ? ?
Вот код C++ для модифицированной быстрой сортировки для генерации наихудшей последовательности:
// g++ -std=c++11 worstCaseQuicksort.cpp && ./a.out
#include <algorithm> // swap
#include <iostream>
#include <vector>
#include <numeric> // iota
int main( void )
{
std::vector<int> v(20); /**< will hold the worst case later */
/* p basically saves the indices of what was the initial position of the
* elements of v. As they get swapped around by Quicksort p becomes a
* permutation */
auto p = v;
std::iota( p.begin(), p.end(), 0 );
/* in the worst case we need to work on v.size( sequences, because
* the initial sequence is always split after the first element */
for ( auto i = 0u; i < v.size(); ++i )
{
/* i can be interpreted as:
* - subsequence starting index
* - current minimum value, if we start at 0 */
/* note thate in the last step iPivot == v.size()-1 */
auto const iPivot = ( v.size()-1 + i )/2;
v[ p[ iPivot ] ] = i;
std::swap( p[ iPivot ], p[i] );
}
for ( auto x : v ) std::cout << " " << x;
}
Результат:
0
0 1
1 0 2
2 0 1 3
1 3 0 2 4
4 2 0 1 3 5
1 5 3 0 2 4 6
4 2 6 0 1 3 5 7
1 5 3 7 0 2 4 6 8
8 2 6 4 0 1 3 5 7 9
1 9 3 7 5 0 2 4 6 8 10
6 2 10 4 8 0 1 3 5 7 9 11
1 7 3 11 5 9 0 2 4 6 8 10 12
10 2 8 4 12 6 0 1 3 5 7 9 11 13
1 11 3 9 5 13 7 0 2 4 6 8 10 12 14
8 2 12 4 10 6 14 0 1 3 5 7 9 11 13 15
1 9 3 13 5 11 7 15 0 2 4 6 8 10 12 14 16
16 2 10 4 14 6 12 8 0 1 3 5 7 9 11 13 15 17
1 17 3 11 5 15 7 13 9 0 2 4 6 8 10 12 14 16 18
10 2 18 4 12 6 16 8 14 0 1 3 5 7 9 11 13 15 17 19
1 11 3 19 5 13 7 17 9 15 0 2 4 6 8 10 12 14 16 18 20
16 2 12 4 20 6 14 8 18 10 0 1 3 5 7 9 11 13 15 17 19 21
1 17 3 13 5 21 7 15 9 19 11 0 2 4 6 8 10 12 14 16 18 20 22
12 2 18 4 14 6 22 8 16 10 20 0 1 3 5 7 9 11 13 15 17 19 21 23
1 13 3 19 5 15 7 23 9 17 11 21 0 2 4 6 8 10 12 14 16 18 20 22 24
В этом есть порядок. Правая сторона - это просто приращение двух, начиная с нуля. На левой стороне также есть порядок. Позвольте форматировать левую сторону для последовательности худшего случая длиной 73 элемента, используя искусство Ascii:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
------------------------------------------------------------------------------------------------------------
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35
37 39 41 43 45 47 49 51 53
55 57 59 61 63
65 67
69
71
Заголовок - это индекс элемента. В первом ряду номера, начинающиеся с 1 и увеличивающиеся на 2, присваиваются каждому второму элементу. Во второй строке то же самое делается для каждого 4-го элемента, в 3-й строке номера присваиваются каждому 8-му элементу и так далее. В этом случае первое значение, которое будет записано в i-й строке, имеет индекс 2 ^ i-1, но для некоторых длин это выглядит немного иначе.
Полученная структура напоминает перевернутое двоичное дерево, узлы которого помечены снизу вверх, начиная с листьев.
Медиана крайнего левого, центрального и правого элементов - это ось
Другой способ - использовать медиану самого левого, центра и правого элемента. В этом случае наихудшим случаем может быть только то, что левая подпоследовательность имеет длину 2 (а не только длину 1, как в примерах выше). Также мы предполагаем, что самое правильное значение всегда будет наибольшим из медианы трех. Это также означает, что это самое высокое из всех значений. Внося коррективы в программу выше, теперь у нас есть это:
auto p = v;
std::iota( p.begin(), p.end(), 0 );
auto i = 0u;
for ( ; i < v.size(); i+=2 )
{
auto const iPivot0 = i;
auto const iPivot1 = ( i + v.size()-1 )/2;
v[ p[ iPivot1 ] ] = i+1;
v[ p[ iPivot0 ] ] = i;
std::swap( p[ iPivot1 ], p[i+1] );
}
if ( v.size() > 0 && i == v.size() )
v[ v.size()-1 ] = i-1;
Сгенерированные последовательности:
0
0 1
0 1 2
0 1 2 3
0 2 1 3 4
0 2 1 3 4 5
0 4 2 1 3 5 6
0 4 2 1 3 5 6 7
0 4 2 6 1 3 5 7 8
0 4 2 6 1 3 5 7 8 9
0 8 2 6 4 1 3 5 7 9 10
0 8 2 6 4 1 3 5 7 9 10 11
0 6 2 10 4 8 1 3 5 7 9 11 12
0 6 2 10 4 8 1 3 5 7 9 11 12 13
0 10 2 8 4 12 6 1 3 5 7 9 11 13 14
0 10 2 8 4 12 6 1 3 5 7 9 11 13 14 15
0 8 2 12 4 10 6 14 1 3 5 7 9 11 13 15 16
0 8 2 12 4 10 6 14 1 3 5 7 9 11 13 15 16 17
0 16 2 10 4 14 6 12 8 1 3 5 7 9 11 13 15 17 18
0 16 2 10 4 14 6 12 8 1 3 5 7 9 11 13 15 17 18 19
0 10 2 18 4 12 6 16 8 14 1 3 5 7 9 11 13 15 17 19 20
0 10 2 18 4 12 6 16 8 14 1 3 5 7 9 11 13 15 17 19 20 21
0 16 2 12 4 20 6 14 8 18 10 1 3 5 7 9 11 13 15 17 19 21 22
0 16 2 12 4 20 6 14 8 18 10 1 3 5 7 9 11 13 15 17 19 21 22 23
0 12 2 18 4 14 6 22 8 16 10 20 1 3 5 7 9 11 13 15 17 19 21 23 24
Псевдослучайный элемент со случайным начальным числом 0 является сводным
Последствия наихудшего случая для центрального элемента и медианы-трех выглядят уже довольно случайными, но для того, чтобы сделать быструю сортировку еще более надежной, элемент поворота можно выбрать случайным образом. Если используемая случайная последовательность, по крайней мере, воспроизводима при каждом запуске быстрой сортировки, то для этого мы также можем построить последовательность наихудшего случая. Нам нужно только отрегулировать строку iPivot = в первой программе, например, в:
srand(0); // you shouldn't use 0 as a seed
for ( auto i = 0u; i < v.size(); ++i )
{
auto const iPivot = i + rand() % ( v.size() - i );
[...]
Сгенерированные последовательности:
0
1 0
1 0 2
2 3 1 0
1 4 2 0 3
5 0 1 2 3 4
6 0 5 4 2 1 3
7 2 4 3 6 1 5 0
4 0 3 6 2 8 7 1 5
2 3 6 0 8 5 9 7 1 4
3 6 2 5 7 4 0 1 8 10 9
8 11 7 6 10 4 9 0 5 2 3 1
0 12 3 10 6 8 11 7 2 4 9 1 5
9 0 8 10 11 3 12 4 6 7 1 2 5 13
2 4 14 5 9 1 12 6 13 8 3 7 10 0 11
3 15 1 13 5 8 9 0 10 4 7 2 6 11 12 14
11 16 8 9 10 4 6 1 3 7 0 12 5 14 2 15 13
6 0 15 7 11 4 5 14 13 17 9 2 10 3 12 16 1 8
8 14 0 12 18 13 3 7 5 17 9 2 4 15 11 10 16 1 6
3 6 16 0 11 4 15 9 13 19 7 2 10 17 12 5 1 8 18 14
6 0 14 9 15 2 8 1 11 7 3 19 18 16 20 17 13 12 10 4 5
14 16 7 9 8 1 3 21 5 4 12 17 10 19 18 15 6 0 11 2 13 20
1 2 22 11 16 9 10 14 12 6 17 0 5 20 4 21 19 8 3 7 18 15 13
22 1 15 18 8 19 13 0 14 23 9 12 10 5 11 21 6 4 17 2 16 7 3 20
2 19 17 6 10 13 11 8 0 16 12 22 4 18 15 20 3 24 21 7 5 14 9 1 23
Итак, как проверить правильность этих последовательностей?
- Измерьте время, которое потребовалось для последовательностей. Время графика по длине последовательности N. Если кривая масштабируется с O (N ^ 2) вместо O (N log (N)), то это действительно наихудшие последовательности.
- Отрегулируйте правильную быструю сортировку, чтобы получить отладочную информацию о длине подпоследовательности и/или выбранных элементах разворота. Одна из подпоследовательностей всегда должна иметь длину 1 (или 2 для медианы-трех). Выбранные элементы разворота должны быть увеличены.
Ответ 3
Получение вершины, равной самому низкому или наибольшему числу, должно также инициировать наихудший сценарий O (n 2).
Ответ 4
Различные реализации quicksort имеют разные наборы данных, необходимые для обеспечения наихудшего времени выполнения. Это зависит от того, где алгоритм выбирает его элемент-поворот.
А также, как сказал Ghpst, выбор самого большого или наименьшего числа даст вам худший случай.
Если я правильно помню, quicksort обычно использует случайный элемент для поворота, чтобы свести к минимуму вероятность получить наихудший случай.
Ответ 5
Я думаю, что если массив находится в порядке revrse, то это будет худший случай для поворота последнего элемента этого массива
Ответ 6
Факторы, способствующие наихудшему сценарию быстрой сортировки, следующие:
- Наихудший случай возникает, когда субмашины полностью не сбалансированы
- Худший случай возникает, когда в одном подмассиве есть 0 элементов и
n-1в другом.
Другими словами, наихудшее время работы quicksort происходит, когда Quicksort принимает отсортированный массив (в порядке убывания), чтобы быть во временной сложности O (n ^ 2).