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.
- Valitse aina ensimmäinen elementti pivotina.
- Valitse pivotiksi aina viimeinen elementti (toteutettu) alla)
- Valitse satunnaiselementti pivotiksi.
- 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.