Miksi valinta lajitellaan nopeammin kuin kuplalajittelu?

Kaikki antamasi monimutkaisuudet pitävät paikkansa, tosin ne annetaan Big O -merkinnässä , joten kaikki lisäarvot ja vakiot jätetään pois.

Vastaamme kysymykseesi d keskittyä näiden kahden algoritmin yksityiskohtaiseen analyysiin. Tämä analyysi voidaan tehdä käsin tai löytyy monista kirjoista. Käytän tuloksia Knuthin tietokoneohjelmointitaidosta .

Keskimääräinen vertailumäärä:

• Kuplalajittelu : $ \ frac {1} {2} (N ^ 2-N \ ln N – (\ gamma + \ ln2 -1) N) + \ mathcal O (\ sqrt N) $
• Lisäosan lajittelu : $ \ frac {1} {4} (N ^ 2-N) + N – H_N $
• Valintalaji : $ (N + 1) H_N – 2N $

Jos piirrät nämä toiminnot, saat jotain tällaista:

Kuten näette, kuplalajittelu on paljon huonompi elementtien määrän kasvaessa, vaikka molemmilla lajittelumenetelmillä on sama asymptoottinen monimutkaisuus.

Tämä analyysi perustuu oletukseen, että syöte on satunnainen – mikä ei ehkä ole totta koko ajan. Ennen kuin aloitamme lajittelun, voimme satunnaisesti perforoida syötesekvenssin (millä tahansa menetelmällä) keskimääräisen tapauksen saamiseksi.

Jättäin aikakompleksianalyysin pois, koska se riippuu toteutuksesta, mutta vastaavia menetelmiä voidaan käyttää.

Kommentit

• Minulla on ongelma ” kanssa, voimme satunnaisesti sallia syöttösekvenssin saadaksemme keskiarvotapauksen ”. Miksi se voidaan tehdä nopeammin kuin lajitteluaika?
• Voit perua minkä tahansa numerosarjan, joka vie $ N $ aikaa, kun $ N $ on jakson pituus. ’ on ilmeistä, että kaikessa vertailupohjaisessa lajittelualgoritmissa on oltava vähintään $ \ mathcal O (N \ log N) $ monimutkaisuus, vaikka lisäät siihen $ N $ ’ monimutkaisuus ei muutu ’ t niin paljon. Joka tapauksessa puhumme vertailusta, ei ajasta, ajan monimutkaisuus riippuu toteutuksesta ja koneesta, kuten mainitsin vastauksessa.
• Luulen, että olin uninen, olet oikeassa, sekvenssi voidaan toistaa lineaarisessa ajassa .
• Koska $ H_N = \ Theta (log N) $, onko vertailusi sidottu oikein valintalajittelua varten? Näyttää siltä, että olet ’ viitannut siihen, että se tekee keskimäärin O (n log n) -vertailuja.
• Gamma = 0,577216 on Euler-Mascheroni ’ s vakio. Asiaankuuluva luku on ” Ohjelmointitaide ” 3. osa 5.2.2 s. 109 ja 129. Kuinka piirrit kuplalajittelutapauksen tarkalleen erityisesti O (sqrt (N)) -termin? Unohditko vain sen?

Asymptoottiset kustannukset tai $ \ mathcal O $ -merkintä, kuvaa funktion rajoittavaa käyttäytymistä, kun sen argumentti pyrkii loputtomuuteen, ts. sen kasvunopeuteen.

Itse toiminto, esim. Vertailujen ja / tai swapien lukumäärä voi olla erilainen kahdelle algoritmille, joilla on sama asymptoottinen hinta, edellyttäen että ne kasvavat samalla nopeudella.

Tarkemmin sanottuna Bubble sort vaatii keskimäärin $ n / 4 $ vaihtaa merkintää kohden (jokainen merkintä siirretään elementtien mukaan alkuperäisestä sijainnistaan lopulliseen sijaintiinsa, ja jokaiseen vaihtoon sisältyy kaksi merkintää), kun taas Valinta-lajittelu vaatii vain $ 1 $ (kun vähimmäis- / enimmäismäärä on löydetty, se vaihdetaan kerran) taulukon loppuun).

Vertailumäärän kannalta Bubble sort vaatii $ k \ kertaa n $ vertailuja, joissa $ k $ on merkinnän alkupaikan ja etäisyyden välinen suurin etäisyys sen lopullinen sijainti, joka on yleensä suurempi kuin $ n / 2 $ tasaisesti jakautuneille alkuarvoille. Valintalajittelu vaatii kuitenkin aina $ (n-1) \ kertaa (n-2) / 2 $ -vertailuja.

Yhteenvetona voidaan todeta, että asymptoottinen raja antaa sinulle hyvän käsityksen siitä, kuinka algoritmin kustannukset kasvavat syötteen kokoon nähden, mutta ei kerro mitään eri algoritmien suhteellisesta suorituskyvystä saman ryhmän sisällä. p>

Kommentit

• tämä on jopa erittäin hyvä vastaus
• mitä kirjaa pidät mieluummin?
• @GrijeshChauhan: Kirjat ovat makukysymys, joten ota kaikki suositukset jyvän suolalla. Pidän henkilökohtaisesti Cormenista, Leisersonista ja Rivestistä ’ s ” Johdatus algoritmeihin ”, joka antaa hyvän yleiskatsauksen useista aiheista, ja Knuth ’ s ” Tietokoneohjelmoinnin taide ” -sarja, jos tarvitset lisätietoja / kaikkia yksityiskohtia mistä tahansa tietystä aiheesta. Haluat ehkä tarkistaa, onko kirjoihin liittyvä kysymys esitetty aiemmin täällä, tai lähettää kysymys, jos se ei ole ’ t.
• Minulle kolmas kohta vastauksesi on todellinen vastaus. Ei suurten syötteiden kuvaajia, jotka on annettu toisessa vastauksessa.

Kuplalajittelu käyttää enemmän vaihtoaikoja, Valintalajittelu välttää tämän.

Kun valitset lajittelun, se vaihtaa korkeintaan n kertaa. mutta kun käytetään kuplalajittelua, se vaihtaa melkein n*(n-1). Ja tietysti lukuaika on vähemmän kuin kirjoitusaika jopa muistissa. Vertailuaika ja muu ajoaika voidaan jättää huomioimatta. Joten vaihtamisajat ovat ongelman kriittinen pullonkaula.

kommentit

• Mielestäni toinen Bartekin vastaus on järkevämpi, mutta en voi ’ äänestää tai kommentti … BTW mielestäni kirjoitusaika vaikuttaa edelleen suurempaan ja toivon, että hän voi ottaa tämän huomioon, jos hän näkee tämän ja on samaa mieltä.
• Et voi yksinkertaisesti jättää huomiotta useita vertailuja, koska on tapauksia, joissa aika Kahden kohteen vertailuun käytetty summa voi ylittää kahden kohteen vaihtamiseen kuluneen ajan. Harkitse linkitettyä luetteloa erittäin pitkistä merkkijonoista (sano 100k merkkiä kukin). Kussakin merkkijonossa lukeminen vie paljon kauemmin kuin osoittimen uudelleenmäärittely.
• @IrvinLim Luulen, että saatat olla oikeassa, mutta minun on ehkä nähdä tilastotiedot, ennen kuin muutan mieltäni. ul>