Paras ja huonoin tapa syötteet kasan lajittelua ja nopeaa lajittelua varten?

kasa – Koska paras ja huonoin tapaus ovat samat eikö sillä ole merkitystä syöttöjärjestyksellä? Vertailujen ja tehtävien lukumäärä on aina sama? Kuvittelin, että kasan lajittelussa se voi olla sama, koska todellinen työ tehdään lisäyksessä, mutta lajittelu käyttää vain max / min kasa? Siksi?

Tehtyjen vertailujen määrä voi riippua järjestys, jossa arvot annetaan. Se, että paras ja pahin tapaus ovat kukin Θ (n log n) – olettaen, että kaikki elementit ovat erillisiä – tarkoittaa vain, että asymptoottisesti ei ole eroa näiden kahden välillä, vaikka ne voivatkin erota vakiokertoimella. Minulla ei ole yksinkertaisia esimerkkejä tästä pääni yläosasta, mutta uskon, että voit rakentaa syötteitä, joissa vertailumäärä eroaa vakiotekijällä kaksi lähestymistapaa. Koska iso-O-merkintätapa jättää vakiot huomiotta, tämä ei näy parhaassa ja pahimmassa tapauksessa.

nopea lajittelu – tämä En tiedä varmasti. En ole varma, mitkä ovat parhaat ja pahimmat tapaukset. Jos esimerkiksi jo lajiteltu 10 merkkijonon luettelo ei ”t, meidän on aina valittava sama määrä kääntöjä rekursiivisen algoritmin täydentämiseksi? Kaikki tämän selityksen ohjeet todella auttavat.

Valittujen kääntöpisteiden määrä on todellakin sama riippumatta algoritmin suorituksesta. Pivot-kohdalla tehty työ voi kuitenkin vaihdella sen mukaan, minkä tyyppiset jaot saat. Parhaassa tapauksessa kussakin vaiheessa valittu kääntö on matriisin mediaanielementti. Kun näin tapahtuu, rekursion yläkerrassa tehdään (karkeasti) n vertailua, sitten (karkeasti) n seuraavalla kerroksella, koska on kaksi ali-palkkia, joiden koko on n / 2, seuraavassa on (karkeasti) n tasoa, koska siellä on neljä aliriviä, joiden koko on n / 4 jne. Koska Θ (log n) kerroksia on ja kukin kerros tekee Θ (n) työ, tehty kokonaismäärä on Θ (n log n). Toisaalta harkitse kunkin taulukon absoluuttisen minimin valitsemista pivotiksi. Sitten (karkeasti) n vertailua tehdään ylemmässä kerroksessa, sitten (karkeasti) n – 1 seuraavassa kerroksessa, sitten (karkeasti) n – 2 seuraavassa kerroksessa jne. Summa 1 + 2 + 3 + … + n on Θ (n ² ), joten pahin tapaus.

Toivottavasti tämä auttaa!

Kommentit

• Sir, miten heapsort nlogn on paras tapa? Jos katsomme, että kaikki elementit ovat identtisiä, kustannukset olisivat vain iterointi taulukon kaikkien elementtien läpi eikä siirtymistä juuriin asti. Joten minun pitäisi olla omega (n).
• Se on hyvä asia. Oletin erillisiä elementtejä, joten päivitän tämän vastauksen.

Koska kukaan ei todella osoitettu heapSort vielä:

Olettaen, että käytät max-kasaa, joka on esitetty matriisina, ja lisäämällä max-elementtisi taaksepäin lähtötaulukkoosi / taulukkosi takaosaan, jos teet sen paikallaan , heapSortin pahin tapaus on mikä tahansa syöte, joka pakottaa sinut ”kuplimaan alas” tai toistamaan uudelleen joka kerta, kun poistat elementin. Tämä tapahtuu joka kerta, kun yrität lajitella sarjaa ilman kopioita. Se on silti Θ (n loki n), kuten templatetypedef sanoi.

Tämä ominaisuus tarkoittaa, että heapSortin paras tapa on, kun kaikki elementit ovat yhtä suuret (Θ (n), koska sinun ei tarvitse toistaa uudelleen jokaisen poiston jälkeen, mikä vie loki (n) aikaa kasan maksimikorkeus on log (n)). Se on kuitenkin eräänlainen surkea / epäkäytännöllinen tapaus, minkä vuoksi todellinen paras tapaus heapsortille on Θ (n log n).

Kommentit

• Algoritmikurssiltani kysyttiin juuri valitettavaa epäkäytännöllistä tapausta. (Varokaa temppukysymyksiä.) Olen tietysti edelleen yhtä mieltä kanssanne. ( ja sain väärän vastaukseni XD)

• Pikalajittelu

  Pahin tapaus: $ \ mathcal {O} (n ^ 2) $ . Oletetaan, että pivot-elementti on aina oikeanpuoleisin elementti: Syötä jo lajiteltu luettelo $ n $ -elementeillä. Jokainen osiointi johtaa siis yhteen luetteloon, jossa on $ n-1 $ -elementtejä ja yhden luettelon, jossa on $ 0 $ -elementtejä. Vaikka valitsisit pivot-elementin satunnaisesti , voit silti olla epäonninen ja valita aina luettelon enimmäisarvo.

  Olkoon $ T (n) $ vertailulukujen määrä vaatii lajittelemaan luettelon $ n $ -elementeillä. Pahin tapaus: \ begin {tasaus} T (n) = & T (n-1) + n & \ text {($ T (n-1) $ rekursiivinen, $ n $ osioon)} \\ = & \ frac {n (n + 1) } {2} \ in \ mathcal {O} (n) \ end {tasaa}

  Paras tapaus: $ \ mathcal {O} (n \ log n) $ . Jos pivot-elementti valitaan siten, että se jakaa luettelon tasaisesti:

  \ begin {tasaus} T (n) = & 2 \ T \ vasen (\ frac {n} {2} \ oikea) + n & (\ text {2 kertaa $ \ frac {n} { 2} $ rekursiivinen, $ n $ osioon)} \\ \ & \ mathcal {O} (n \ log n) & (\ text {master theorem}) \ end {align}

• Heap Sort

  Pino- ja parhaan tapauksen monimutkaisuus kasan lajittelussa ovat molemmat $ \ mathcal {O} (n \ log n) $ . Siksi kasan lajittelu edellyttää $ \ mathcal {O} (n \ log n) $ vertailua mille tahansa syötetaulukolle. Kasan lajittelun monimutkaisuus:

  \ begin {align} & \ mathcal {O} (n) & (\ text {build $ (1, n) $ kasa}) \\ + & \ sum_ {i = 1} ^ {n} \ mathcal {O} (\ log i – \ log 1) & (\ text {koota $ (1, j) $ kasa}) \\ = & \ mathcal {O} (n) + \ sum_ {i = 1} ^ {n} \ mathcal {O} (\ log i) & (\ teksti {logaritmin osamääräsääntö}) \\ = & \ mathcal {O} (n \ log n) & \ left (\ summa_ {i = 1} ^ {n} \ log i < \ sum_ {i = 1} ^ {n} \ log n = n \ log n \ right) \ end {tasaa }

kommentit

• Sinulla ei ole ’ t vastasin kaikkiin OP ’ -kysymyksiin, joten vastaan niihin, jotka menetit; kasan lajittelu ei ’ t käytä aina samaa määrää vertailuja tietylle määrälle elementtejä. Pahin tapaus on $ a \, n \ log n $ ja paras tapaus on $ b \, n \ log n $, jossa $ a > b $.
• Huomaa myös, että kolmitievaihtoehdolla on lineaarinen paras tapa yksittäisten elementtien syötölle.