Nejlepší odpověď
Jelikož máte dostatečné znalosti o tom, jak rychlé řazení funguje, jako je hledání pivotů, rozdělení aktuálního pole a opětovné provádění stejné rekurzivně pro každé dílčí pole, je snadné analyzovat časovou složitost s ohledem na tyto věci:
Nejhorší případ:
Nejhorší případ nastane, když při každé rekurzi dostaneme další pivot, který rozděluje pole na konec pole.
Pokud N je délka pole a má aktuální pivot na počáteční pozici pole,
pivot na posledním indexu je identifikován pouze procházející pole od začátku do konce. Po opravě otočení a rozdělení výsledných dílčích polí délky jsou (N-1), 1 .
Opět toto (N-1) dílčí pole najde další otočení na posledním indexu, čímž vzniknou oddíly pole s délkami (N-2), 1 .
Tento proces se opakuje, dokud nejsou konečné délky dílčích polí 1,1 .
Takže, toto lze matematicky nakreslit na papír jako
v kroku 1: s N prvky je časová složitost pro tento oddíl
T (N) = N + T (N-1)
Kde T (N-1) je časová složitost oddílu být zpracován rekurzivně a N je čas potřebný k porovnání N prvků s pevným pivotem.
v kroku 2: s N-1 prvky ,
T (N-1) = (N-1) + T (N-2)
T (N-2) = (N-2) + T (N-3)
…
T (3) = 3 + T (2)
T (2) = 2 + T (1)
T ( 1) = 0, protože čas pro rozdělení pole s délkou „1“ je 0 bez oddílů
Proto
T (N) = N + (N-1) + (N-2) … + 3 + 2 ≈ N * (N + 1) / 2
= (N ^ 2) / 2
= O (N ^ 2)
průměrný případ :
V průměrném případě další pivot rozdělí pole na dvě stejné délky (N / 2) porovnáním všechny prvky, jejichž výsledkem je časová složitost N.
T (N) = 2 * T (N / 2) + N
rozdělit obě strany číslem N
T (N) / N = 2 * (T (N / 2) / N) + N / N
T (N) / N = 2 * (T (N / 2) / N) + 1
Proto T (N) / N = (T (N / 2) / (N / 2)) + 1
T (N / 2) / (N / 2) = T (N / 4) / (N / 4) + 1
…
T (2) / 2 = T (1) / 1 + 1
Jako T (1) = 0
T (2) / 2 = 1
T (4) / 4 = T (2) + T (1)
T (8) / 8 = T (4) + T (2) + T (1) ## log (n) termíny
Proto T (N) / N = log N
T (N) = NlogN
Odpověď
QuickSort je algoritmus Divide and Conquer. Vybírá prvek jako pivot a rozděluje dané pole kolem vybraného pivot. Existuje mnoho různých verzí quickSortu, které vybírají pivot různými způsoby.
- Vždy vyberte první prvek jako pivot.
- Vždy vyberte poslední prvek jako pivot (implementováno níže)
- Vyberte náhodný prvek jako pivot.
- Vyberte medián jako pivot.
Klíčovým procesem v quickSortu je oddíl ( ). Cíl oddílů je, vzhledem k poli a prvku x pole jako otočnému čepu, dát x na správnou pozici v seřazeném poli a dát všechny menší prvky (menší než x) před x a dát všechny větší prvky (větší než x) po x. To vše by mělo být provedeno v lineárním čase.
Kroky rychlého řazení jsou:
Step 1 − Choose the highest index value has a pivot
Step 2 − Take two variables to point left and right of the list excluding pivot
Step 3 − left points to the low index
Step 4 − right points to the high
Step 5 − while value at left is less than pivot move right
Step 6 − while value at the right is greater than pivot move left
Step 7 − if both step 5 and step 6 does not match swap left and right
Step 8 − if left ≥ right, the point where they met is the new pivot
Implementace rychlého řazení:
Quicksort(A,p,r) {
if (p
q
Quicksort(A,p,q)
Quicksort(A,q+1,r)
}
}
Partition(A,p,r)
x
i
j
while (True) {
repeat
j
until (A[j]
i
until (A[i] >= x)
if (i A[j]
else
return(j)
}
}
Časová složitost rychlého řazení:
nejhorší Případ: Nejhorší případ nastane, když proces oddílu vždy vybere největší nebo nejmenší prvek jako otočný. Pokud vezmeme v úvahu výše uvedenou strategii rozdělení, kde je poslední prvek vždy vybrán jako pivot, nejhorší případ by nastal, když je pole již tříděno ve vzestupném nebo sestupném pořadí. Následuje opakování pro nejhorší případ.
T(n) = T(0) + T(n-1) + (n)
which is equivalent to
T(n) = T(n-1) + (n)
Složitost výše uvedeného opakování je čtverec
Nejlepší případ: Nejlepší případ nastane, když proces oddílu vždy vybere střední prvek jako pivot. Následuje opakování pro nejlepší případ.
T(n) = 2T(n/2) + (n)
Složitost výše uvedeného opakování je nLogn
Průměrný případ: Abychom provedli analýzu průměrných případů, musíme vzít v úvahu veškerou možnou permutaci pole a vypočítat čas potřebný pro každou permutaci, která nevypadá snadno. Můžeme získat představu o průměrném případě zvážením případu, kdy oddíl umístí prvky O (n / 9) do jedné sady a prvky O (9n / 10) do jiných sad. Následuje opakování pro tento případ.
T(n) = T(n/9) + T(9n/10) + (n)
Složitost výše uvedeného opakování je nLogn
Prostorová složitost rychlého řazení :
Prostor využívaný quicksortem závisí na použité verzi.
Místní verze quicksortu má prostorovou složitost O (log n), dokonce i v nejhorší případ, když je pečlivě implementován pomocí následujících strategií:
- Je použito místní dělení. Tento nestabilní oddíl vyžaduje prostor O (1).
- Po rozdělení je oddíl s nejmenším počtem prvků (rekurzivně) seřazen jako první, což vyžaduje maximálně prostor O (log n). Potom je druhý oddíl tříděn pomocí rekurze nebo iterace ocasu, což nepřidává do zásobníku volání. Tato myšlenka, jak byla diskutována výše, byla popsána R. Sedgewickem a udržuje hloubku zásobníku ohraničenou O (log n).