Mi a gyors rendezés időbeli összetettsége?

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.

  1. Mindig az első elemet válassza ki pivotként.
  2. Mindig az utolsó elemet válassza ki pivotként (implementálva) alább)
  3. Válasszon véletlenszerű elemet pivotként.
  4. 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>

Vélemény, hozzászólás?

Az email címet nem tesszük közzé. A kötelező mezőket * karakterrel jelöltük