Legjobb válasz
Mivel elegendő ismerete van a Gyorsrendezés működéséről, például pivot kereséséről, az aktuális tömb felosztásáról és újra ugyanazon rekurzív módon az egyes tömböknél, könnyen elemezhető az idő bonyolultsága, figyelembe véve ezeket a dolgokat:
Legrosszabb eset:
A legrosszabb eset akkor következik be, amikor minden rekurziónál a tömb végén lévő osztott tömbök következő pivotját kapjuk.
Ha N a tömb hossza, és az aktuális elfordulás a tömb kiindulási helyzetében van,
az utolsó index a pivotot csak a tömbtől az elejétől a végéig haladja meg. A forgatás és az osztás kijavítása után az eredményezett rész tömbök (N-1), 1 .
Ismét ez (N-1) altömb megtalálja a következő pivot-ot az utolsó indexben, és (N-2), 1 span hosszúságú tömbpartíciókat talál >.
Ez a folyamat addig ismétlődik, amíg az utolsó résztömbök hossza 1,1 .
Tehát, ez matematikailag papírba rajzolható
az 1. lépésben: N elemekkel a partíció időbonyolultsága
T (N) = N + T (N-1)
Ahol T (N-1) a partíció időbeli összetettsége rekurzív módon kerül feldolgozásra, és N az az idő, amely ahhoz szükséges, hogy N elemet fix rögzítéssel összehasonlítsunk.
a 2. lépésben: N-1 elemekkel ,
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, mivel az 1 hosszúságú tömb partíciójának ideje 0, partíciók nélkül
Ezért
T (N) = N + (N-1) + (N-2) … + 3 + 2 ≈ N * (N + 1) / 2
= (N ^ 2) / 2
= O (N ^ 2)
Átlagos eset :
Átlagos esetben a következő pivot tömböt két egyenlő hosszúságra osztja fel (N / 2) összehasonlítással minden elem, amely az idő komplexitását eredményezi N.
T (N) = 2 * T (N / 2) + N
ossza el mindkét oldalt N
T (N) / N = 2 * (T (N / 2) / N) + N / N
T (N) / N = 2 * (T (N / 2) / N) + 1
Ezért 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
As 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) kifejezések
Ezért T (N) / N = log N
T (N) = NlogN
Válasz
A QuickSort egy Divide and Conquer algoritmus. Kiválaszt egy elemet pivotként, és particionálja az adott tömböt a kiválasztott pivot köré. A quickSort számos különböző verziója különböző módon választja ki a pivot.
- Mindig az első elemet válassza ki pivotként.
- Mindig az utolsó elemet válassza ki pivotként (implementálva) alább)
- Válasszon véletlenszerű elemet pivotként.
- Válassza ki a mediánt pivotként.
A quickSort kulcsfontosságú folyamata egy partíció ( ). A partíciók célpontjának megadva egy tömböt és a tömb x elemét elfordulva, az x-et a megfelelő helyzetbe helyezzük egy rendezett tömbben, és az összes kisebb elemet (x-nél kisebb) x elé tesszük, és az összes nagyobb elemet (nagyobb mint x) x után. Mindezt lineáris időben kell elvégezni.
A quicksort lépései:
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
Quicksort megvalósítása:
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)
}
}
A quicksort időbeli összetettsége:
Legrosszabb Eset: A legrosszabb eset akkor következik be, amikor a partíciós folyamat mindig a legnagyobb vagy a legkisebb elemet választja el pivotként. Ha figyelembe vesszük a fenti partíciós stratégiát, ahol az utolsó elem mindig pivotként kerül kiválasztásra, akkor a legrosszabb eset akkor következne be, ha a tömb már növekvő vagy csökkenő sorrendbe van rendezve. A következő a legrosszabb esetben is megismétlődik.
T(n) = T(0) + T(n-1) + (n)
which is equivalent to
T(n) = T(n-1) + (n)
A fenti megismétlődés összetettsége n négyzet
Legjobb eset: A legjobb eset akkor következik be, amikor a partíció folyamata mindig kiválasztja a középső elem pivotként. A következők a legjobb esetben ismétlődnek.
T(n) = 2T(n/2) + (n)
A fenti megismétlődés összetettsége nLogn
Átlagos eset: Az átlagos esetelemzéshez meg kell vizsgálnunk a tömb minden lehetséges permutációját, és ki kell számolnunk az egyes permutációk által elért időt, ami nem tűnik egyszerűnek. Az átlagos esetről képet kaphatunk, ha megvizsgáljuk azt az esetet, amikor a partíció O (n / 9) elemeket egy halmazba, O (9n / 10) elemeket pedig más halmazokba rak. Az alábbiakban megismétlődik ez az eset.
T(n) = T(n/9) + T(9n/10) + (n)
A fenti megismétlődés összetettsége nLogn
A quicksort térbeli összetettsége :
A quicksort által használt terület a használt verziótól függ.
A quicksort helybeli verziójának O (log n) térbeli összetettsége még az a legrosszabb esetben, amikor gondosan megvalósítják a következő stratégiák segítségével:
- helyben történő particionálást alkalmaznak. Ehhez az instabil partícióhoz O (1) hely szükséges.
- A particionálás után a legkevesebb elemet tartalmazó partíciót először (rekurzívan) rendezik, legfeljebb O (log n) helyet igényel. Ezután a másik partíciót farokrekurzióval vagy iterációval rendezik, amelyek nem adódnak a hívásveremhez. Ezt az ötletet, ahogy fentebb tárgyaltuk, R. Sedgewick írta le, és a verem mélységét O (log n) határolja. / li>