Анализ на бързо сортиране

Защо най-лошото време за изпълнение и средното време на изпълнение на бързото сортиране се различават? За начало да разгледаме най-лошото време за изпълнение. Да предположим, че нямаме късмет и размерите на частите не са балансирани. В конкретния случай да предположим, че оста, избрана от функцията partition, винаги е или най-малкият, или най-големият елемент в подмасива от $n$‍ елемента. Тогава едната част няма да има елементи, а другата ще съдържа $n-1$‍ елементи – всички без оста. Така рекурентните извиквания ще бъдат върху подмасиви с размери 0 и $n-1$‍.

Както е при сортирането чрез сливане, времето за дадено рекурентно извикване върху подмасив с $n$‍ елемента е $\mathrm{\Theta }(n)$‍. В сортирането чрез сливане това е времето за сливане, но в бързото сортиране, това е времето за разделяне.

Когато бързото сортиране има възможно най-небалансирано разделяне за всички случаи, първоначалното време е $cn$‍ за някаква константа $c$‍, рекурентното извикване върху $n-1$‍ елемента отнема време $c(n-1)$‍, рекурентното извикване върху $n-2$‍ отнема време $c(n-2)$‍ и т.н. Ето едно дърво с размерите на подзадачите и времето за тяхното разделяне:

Когато съберем времето за разделяне на всяко ниво, получаваме

Последният ред се дължи на това, че $1+2+3+\cdots +n$‍ е артиметична прогресия, както видяхме в анализа на сортирането чрез пряка селекция. (За бързото сортиране вадим 1, защото сумирането започва от 2, а не от 1.) Имаме някои членове от нисък порядък и константни коефициенти, но, когато използваме нотацията big-Θ, ги игнорираме. В нотацията big-Θ най-лошото време за изпълнение на бързо сортиране е $\mathrm{\Theta }(n^2)$‍.

Най-добрият случай на бързото сортиране се случва, когато частите са възможно най-балансирани: имат еднакъв размер или размерите им се различават с 1. Първият случай се проявява, когато подмасивът има нечетен брой елементи, а оста се намира в средата след разделянето и всяка част има по $(n-1)/2$‍ елемента. Вторият случай се проявява, когато подмасивът има четен брой $n$‍ елементи и едната част има $n/2$‍ елемента, а другата $n/2-1$‍. И в двата случая всяка част има най-много $n/2$‍ елемента, а размерите на трите подзадачи приличат много на размерите на подзадачите при сортирането чрез сливане, а времето за разделяне прилича на времето за сливане:

Използваме нотацията big-Θ и получаваме същия резултат като при сортиране чрез сливане: $\mathrm{\Theta }(n{\log }_{2}n)$‍.

Доказателството, че средното време за изпълнение също е $\mathrm{\Theta }(n{\log }_{2}n)$‍ изисква доста сложни математически изчисления, затова няма да го правим. Можем обаче да разгледаме няколко други случая, за да разберем защо може да е $O(n{\log }_{2}n)$‍. (Когато имаме $O(n{\log }_{2}n)$‍, следва границата $\mathrm{\Theta }(n{\log }_{2}n)$‍, защото средното време за изпълнение не може да е по-добро от най-доброто време за изпълнение.) Първо да си представим, че не винаги имаме добре балансирани части, а винаги имаме най-лошото разделяне 3 към 1. Т.е. представи си, че винаги едната част получава $3n/4$‍ от елементите, а другата част получава $n/4$‍. (За по-лесни изчисления няма да взимаме предвид оста.) Тогава дървото на размерите на подзадачите и времената за разделяне изглеждат така:

Лявата част на всеки възел получава елементите с размер 1/4, а дясната част получава елементите с размер 3/4 от подзадачите. Тъй като по-малките подзадачи са отляво, ако се движим само в лявата посока, ние стигаме от основата до подзадачи с размер единица по-бързо, отколкото по който и да е друг път.Както се вижда от диаграмата, след ${\log }_{4}n$‍ нива ние достигаме до подзадача с размер 1. Защо след ${\log }_{4}n$‍ нива? По-лесно е да си представим, че тръгваме от подзадача с размер 1 и умножаваме по 4, докато стигне до $n$‍. С други думи търсим за коя стойност на $x$‍ е изпълнено $4^x=n$‍? Отговорът е ${\log }_{4}n$‍. Какво се случва, ако се движим само надясно? Диаграмата показва, че са необходими ${\log }_{4/3}n$‍ нива, за да стигнем до подзадача с размер 1. Защо ${\log }_{4/3}n$‍ нива? Тъй като всеки избор отдясно има размер, равен на 3/4 от размера на възела над него (неговия родителски възел), всеки родител е с размер 4/3 по размера на неговото дете. Нека отново си представим, че тръгваме от подзадача с размер 1 и да умножаваме размера по 4/3, докато достигнем $n$‍. За каква стойност на $x$‍ е изпълнено $(4/3{)}^x=n$‍? Отговорът е ${\log }_{4/3}n$‍.

На всяко от първите ${\log }_{4}n$‍ нива има $n$‍ възела (тук отново се включват и осите, които реално повече няма да се разделят), така че общото време за разделяне на всяко от тези нива е $cn$‍. Какво можем да кажем за останалите нива? Възлите във всяко от тях са по-малко от n, следователно времето за разделяне на всяко ниво е най-много $cn$‍. Общо има ${\log }_{4/3}n$‍ нива и затова общото време за разделяне е $O(n{\log }_{4/3}n)$‍. От математиката знаем, че

за всички положителни числа $a$‍, $b$‍ и $n$‍. Ако $a=4/3$‍ и $b=2$‍, получаваме

тогава ${\log }_{4/3}n$‍ и ${\log }_{2}n$‍ се различават само по коефициента ${\log }_2(4/3)$‍, който е константа. Тъй като константните коефициенти не влияят, когато използваме нотацията big-O, можем да кажем, че ако всички разделяния са в пропорция 3 към 1, то времето за изпълнение на бързото сортиране е $O(n{\log }_{2}n)$‍, макар че има по-голям скрит константен коефициент в сравнение с най-доброто време за изпълнение.

Колко често можем да очакваме разделяне в пропорция 3 към 1 или по-добра? Зависи как избираме оста. Нека си представим, че оста е еднакво вероятно да завърши някъде около $n$‍-тия подмасив след разделянето. Тогава за да имаме деление в пропорция 3 към 1 или по-добра, оста трябва да бъде някъде в "средната половина":

Ако за оста е еднакво вероятно да бъде където и да е след разделянето, има 50% възможност за получаване в най-лошия случай на деление 3 към 1. С други думи, очакваме деление 3 към 1 или по-добро в около половината от случаите.

Другият случай, който ще разгледаме, за да разберем защо средното време за изпълнение на бързото сортиране е $O(n{\log }_{2}n)$‍, е какво ще се случи, ако през половината от времето не получим разделяне 3 към 1, а получим най-лошият случай на разделяне. Да предположим, че 3 към 1 и най-лошият случай се редуват и да помислим за връх на дървото с $k$‍ елементи в подмасива. След това ще видим част от дървото, която изглежда така:

вместо така:

Следователно дори ако получаваме най-лошото разделяне през половината от времето и разделяне 3 към 1 или по-добро през другата половина, времето за изпълнение ще бъде около два пъти времето при раделяне 3 към 1 всеки път. Отново, това е константен коефициент и се игнорира при нотацията big-O, затова в случая, когато редуваме най-лошото разделяне и разделяне 3 към 1, времето за изпълнение е $O(n{\log }_{2}n)$‍.

Имай предвид, че този анализ не е математически точен, но дава идея защо средното време за изпълнение може да е $O(n{\log }_{2}n)$‍.

Да предположим, че най-лошият ти враг ти е дал масив, който да сорираш с бързо сортиране, като знае, че винаги избираш за ос най-десния елемент във всеки подмасив и е подредил масива така, че винаги да получаваш най-лошия случай на раделяне. Как ще победиш врага си?

Не е задължително винаги да избираш за ос най-десния елемент от подмасива. Вместо това можеш да избираш случаен елемент от подмасива и да го използваш за ос. Но почакай – функцията partition приема, че оста е най-десният елемент от подмасива. Няма проблем – просто размени елемента, който избираш за ос, с най-десния елемент, а след това раздели, както преди. Ако врагът ти не знае как да избира случайни позиции в подмасива, ти ще спечелиш!

Всъщност, с малко повече усилия, можеш да подобриш шансовете си за получаване на деление с пропорция по-добра от 3 към 1. Избери наслуки не един, а три елемента от подмасива и вземи медианата на трите за ос (като я размениш с най-десния елемент). Под медиана, имаме предвид елемента от трите, чиято стойност е в средата. Няма да разгледаме защо сега, но ако избереш медианата на три случайно избрани елемента за ос, имаш 68,75% шанс (11/16) да получиш деление 3 към 1 или по-добро. Можеш да направиш и повече. Ако избереш наслуки пет елемента и вземеш медианата им за ос, шансовете ти да получиш деление 3 към 1 в най-лошия случай се подобряват и стигат до 79,3% (203/256). Ако вземеш медианата на седем случайно подбрани елемента, шансовете стигат 85,9% (1759/2048). Медиана на 11 елемента? Около 93,1% (488293/524288). Добиваш представа. Разбира се не излиза на сметка да избереш наслуки огромен брой елементи и да вземеш медианата им, тъй като времето, което ще ти отнеме да го направиш, ще се неутрализира с времето, което ще спестиш, за да получиш добри деления през почти цялото време.

Това съдържание е резултат от съвместната дейност на преподавателите по Компютърни науки в Дартмут Thomas Cormen и Devin Balkcom, както и на екипа по компютърни науки на Кан Академия. Съдържанието е лицензирано CC-BY-NC-SA.