Mikä on pikalajittelun aika monimutkaisuus?

Paras vastaus

Koska sinulla on riittävästi tietoa pikalajittelun toiminnasta, kuten pivotin löytäminen, nykyisen taulukon jakaminen ja uudelleen tekeminen sama rekursiivisesti jokaiselle alaryhmälle, on helppo analysoida ajan monimutkaisuus näillä seikoilla:

Pahin tapaus:

Pahin tapaus tapahtuu, kun jokaisella rekursiolla saamme seuraavan pivotin jaettuihin matriiseihin taulukon lopussa.

Jos N on matriisin pituus ja sillä on nykyinen kääntö taulukon alkuasennossa,

viimeisen indeksin kääntö tunnistetaan vain matriisin läpi alusta loppuun. Korjaamisen jälkeen pivot ja jakaminen tuloksena olevat alaryhmät ovat (N-1), 1 .

Jälleen tämä (N-1) -alaryhmä etsii seuraavan pivot-indeksin viimeisestä hakemistosta, jolloin tuloksena on taulukko-osiot, joiden pituus on (N-2), 1 .

Tämä prosessi toistuu, kunnes lopulliset alaryhmät ovat molemmat 1,1 .

Joten, tämä voidaan piirtää matemaattisesti paperiksi

vaiheessa 1: N -elementtien kanssa, tämän osion aikakompleksi on

T (N) = N + T (N-1)

Missä T (N-1) on osion aikakompleksi käsitellään rekursiivisesti ja N on aika, joka tarvitaan N elementin vertaamiseen kiinteään kääntöön.

vaiheessa 2: N-1 -elementtien kanssa ,

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, koska aika osion matriisiin, jonka pituus on 1, on 0 ilman osioita

Siksi

T (N) = N + (N-1) + (N-2) … + 3 + 2 ≈ N * (N + 1) / 2

= (N ^ 2) / 2

= O (N ^ 2)

Keskimääräinen tapaus :

Keskitapauksessa seuraava pivot jakaa matriisin kahteen yhtä pituuteen (N / 2) vertaamalla kaikki elementit, jotka johtavat ajan monimutkaisuuteen N.

T (N) = 2 * T (N / 2) + N

jaa molemmat puolet N

T (N) / N = 2 * (T (N / 2) / N) + N / N

T (N) / N = 2 * (T (N / 2) / N) + 1

Siksi 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

Koska 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) termit

Siksi T (N) / N = log N

T (N) = NlogN

Vastaa

QuickSort on Divide and Conquer -algoritmi. Se valitsee elementin pivotiksi ja osioi annetun taulukon valitun pivotin ympärille. QuickSortissa on monia eri versioita, jotka valitsevat pivotin eri tavoin.

  1. Valitse aina ensimmäinen elementti pivotina.
  2. Valitse pivotiksi aina viimeinen elementti (toteutettu) alla)
  3. Valitse satunnaiselementti pivotiksi.
  4. Valitse mediaani pivotiksi.

quickSortin avainprosessi on osio ( ). Osioiden kohteelle annetaan taulukko ja matriisin elementti x saranana, x asetetaan oikeaan paikkaan lajiteltuun ryhmään ja kaikki pienemmät elementit (pienemmät kuin x) ennen x: tä ja kaikki suuremmat elementit (suurempi kuin x) x: n jälkeen. Kaikki tämä tulisi tehdä lineaarisessa ajassa.

Quicksortin vaiheet ovat:

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

pikalajikkeen toteutus:

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)

}

}

Pikalajittelun ajan monimutkaisuus:

Pahin Tapaus: Pahin tapaus tapahtuu, kun osiointiprosessi valitsee aina suurimman tai pienimmän elementin pivotiksi. Jos otetaan huomioon yllä oleva osiostrategia, jossa viimeinen elementti valitaan aina pivotina, pahin tapaus tapahtuisi, kun matriisi on jo lajiteltu kasvavassa tai laskevassa järjestyksessä. Seuraava on toistuminen pahimmassa tapauksessa.

T(n) = T(0) + T(n-1) + (n)

which is equivalent to

T(n) = T(n-1) + (n)

Yllä olevan toistumisen monimutkaisuus on n neliö

Paras tapaus: Paras tapa tapahtuu, kun osiointiprosessi valitsee aina keskielementti pivotina. Seuraava on parhaan tapauksen toistuminen.

T(n) = 2T(n/2) + (n)

Yllä olevan toistumisen monimutkaisuus on nLogn

Keskimääräinen tapaus: Keskimääräisen tapausanalyysin tekemiseksi meidän on otettava huomioon taulukon kaikki mahdolliset permutaatiot ja laskettava jokaisen permutaation aika, joka ei näytä helpolta. Saamme käsityksen keskimääräisestä tapauksesta tarkastelemalla tapausta, jossa osio asettaa O (n / 9) elementit yhteen sarjaan ja O (9n / 10) elementit muihin sarjoihin. Seuraava on tämän tapauksen toistuminen.

T(n) = T(n/9) + T(9n/10) + (n)

Yllä olevan toistumisen monimutkaisuus on nLogn

Quicksortin tilan monimutkaisuus :

Quicksortin käyttämä tila riippuu käytetystä versiosta.

Quicksortin paikallisessa versiossa on tilan monimutkaisuus O (log n), jopa pahimmassa tapauksessa, kun se toteutetaan huolellisesti seuraavilla strategioilla:

  • käytetään osiointia paikan päällä. Tämä epävakaa osio vaatii O (1) -tilaa.
  • Osioinnin jälkeen vähiten elementtejä sisältävä osio lajitellaan ensin (rekursiivisesti), mikä vaatii enintään O (log n) -tilan. Sitten toinen osio lajitellaan hännän rekursiolla tai iteraatiolla, jota ei lisätä puhelupinoon. Tämän ajatuksen, kuten edellä keskusteltiin, kuvasi R. Sedgewick ja pitää pinon syvyyden O: n (log n) rajoitteena.

Vastaa

Sähköpostiosoitettasi ei julkaista. Pakolliset kentät on merkitty *