Vertailulaji
| n | ⌈ log 2 (n ! )⌉ {\displaystyle \left\lceil \log _ {2} (n!) \ right\rceil }
 |
vähintään |
|---|---|---|
| 1 | 0 | 0 |
| 2 | 1 | 1 |
| 3 | 3 | 3 |
| 4 | 5 | 5 |
| 5 | 7 | 7 |
| 6 | 10 | 10 |
| 7 | 13 | 13 |
| 8 | 16 | 16 |
| 9 | 19 | 19 |
| 10 | 22 | 22 |
| 11 | 26 | 26 |
| 12 | 29 | 30 |
| 13 | 33 | 34 |
| 14 | 37 | 38 |
| 15 | 41 | 42 |
| 16 | 45 | 45 tai 46 |
| 17 | 49 | 49 tai 50 |
| 18 | 53 | 53 tai 54 |
| 19 | 57 | 58 |
| 20 | 62 | 62 |
| 21 | 66 | 66 |
| 22 | 70 | 71 |
| n | ⌈ log 2 (n ! )⌉ {\displaystyle \left\lceil \log _ {2} (n!) \ right\rceil }
|
n log 2 n-n Ln 2 {\displaystyle N\log _{2}n – {\frac {n}{\ln 2}}}
 |
| 10 | 22 | 19 |
| 100 | 525 | 521 |
| 1 000 | 8 530 | 8 524 |
| 10 000 | 118 459 | 118 451 |
| 100 000 | 1 516 705 | 1 516 695 |
| 1 000 000 | 18 488 885 | 18 488 874 |
niiden vertailujen todelliseen vähimmäismäärään (OEIS: a036604), jotka vaaditaan n-alkioiden luettelon järjestämiseksi (pahimmassa tapauksessa). Alla: Stirlingin approksimaation avulla tätä alarajaa approksimoi hyvin n log 2 n-n Ln 2 {\displaystyle N\log _{2}n – {\frac {n}{\ln 2}}}
.
vertailualgoritmin vaatimien vertailujen määrä kasvaa suhteessa n log ( n ) {\displaystyle N\log (n)}
, jossa n {\displaystyle n}
on järjestettävien elementtien määrä. Tämä sidos on asymptoottisen tiukka.
kun otetaan huomioon erillisten lukujen luettelo (voidaan olettaa, koska kyseessä on huonoin mahdollinen analyysi), on olemassa n factorial permutaatioita, joista täsmälleen yksi on luettelo lajitellussa järjestyksessä. Lajittelualgoritmin on saatava vertailuista riittävästi tietoa oikean permutaation tunnistamiseksi. Jos algoritmi täydentyy aina korkeintaan f(n) – vaiheiden jälkeen, se ei voi erottaa enempää kuin 2f(n) – tapauksia, koska avaimet ovat erillisiä ja jokaisella vertailulla on vain kaksi mahdollista lopputulosta. Siksi
2 f (n ) ≥ n ! {\displaystyle 2^{f (n)}\geq n!}
tai vastaavasti f (n ) ≥ log 2 (n ! ) . {\displaystyle f(n)\geq \log _{2} (n!).}
tarkastelemalla ensimmäistä N / 2 {\displaystyle n/2}
n tekijät ! = N (n − 1 ) ⋯ 1 {\displaystyle n!=n (n-1)\cdots 1}
, saadaan log 2 (n ! ) ≥ log 2 ( ( n 2) n 2) = n 2 log n log 2 − n 2 = Θ ( n log n). {\displaystyle \log _ {2} (n!) \geq \log _{2}\left(\left({\frac {n}{2}}\right)^{\frac {n}{2}}\right)={\frac {n}{2}}{\frac {\log n}{\log 2}}-{\frac {n}{2}}=\Theta (n\log n).}
log 2 (n ! ) = Ω (n log n). {\displaystyle \log _ {2} (n!) =\Omega (n\log n).}
näin saadaan vaatimuksen alaraja. Parempi sidos voidaan antaa Stirlingin approksimaation kautta.
identtinen yläraja seuraa siitä, että on olemassa algoritmeja, jotka saavuttavat tämän rajan pahimmassa tapauksessa, kuten heapsort ja mergesort.
edellä esitetty argumentti tarjoaa absoluuttisen, eikä vain asymptoottisen alarajan vertailujen lukumäärälle, nimittäin ⌈ log 2 (n ! )⌉ {\displaystyle \left\lceil \log _ {2} (n!) \ right \ rceil }
vertailut. Tämä alaraja on melko hyvä (sitä voidaan lähestyä lineaarisen toleranssin sisällä yksinkertaisella yhdistämistavalla), mutta sen tiedetään olevan epätarkka. Esimerkiksi ⌈ log 2 (13 ! )⌉ = 33 {\displaystyle \left\lceil \log _{2} (13!) \ right \ rceil =33}
, mutta pienin määrä vertailuja lajitella 13 elementtiä on osoittautunut olevan 34.
tietyn merkintämäärän lajitteluun tarvittavien vertailujen tarkan määrän määrittäminen on laskennallisesti vaikea ongelma pienellekin n: lle, eikä ratkaisulle tunneta yksinkertaista kaavaa. Joidenkin laskettujen konkreettisten arvojen osalta ks.OEIS: A036604.
vertailulukujen keskiarvon alaraja
vastaava raja pätee vertailulukujen keskiarvoon. Olettaen, että
- kaikki avaimet ovat erillisiä, eli jokainen vertailu antaa joko a>b tai a<b, ja
- tulo on satunnainen permutaatio, joka valitaan tasaisesti kaikkien mahdollisten n-alkuaineiden permutaatioiden joukosta,
on mahdotonta määrittää, missä järjestyksessä tulo on alle log2(n!) vertailuja keskimäärin.
tämä on helpoimmin nähtävissä informaatioteorian käsitteiden avulla. Tällaisen satunnaisen permutaation Shannonin entropia on log2 (n!) bittinen. Koska vertailu voi antaa vain kaksi tulosta, sen tarjoaman tiedon enimmäismäärä on 1 bitti. Siksi k-vertailujen jälkeen permutaation jäljelle jäävä entropia on näiden vertailujen tulosten perusteella vähintään log2 (n!)- k bittiä keskimäärin. Lajittelun suorittamiseen tarvitaan täydelliset tiedot, joten jäljelle jäävän entropian on oltava 0. Tästä seuraa, että k: n on oltava vähintään log2 (n!) keskimäärin.
informaatioteorian kautta johdettu alaraja on muotoiltu muotoon “informaatioteoreettinen alaraja”. Informaatioteoreettinen alaraja on oikea, mutta ei välttämättä vahvin alaraja. Ja joissakin tapauksissa ongelman informaatioteoreettinen alaraja voi olla jopa kaukana todellisesta alarajasta. Esimerkiksi informaatioteoreettinen valinnan alaraja on ⌈ log 2 (n)⌉ {\displaystyle \left\lceil \log _{2}(n)\right\rceil }
kun taas n − 1 {\displaystyle n-1}
vertailua tarvitaan kontradiktorisella argumentilla. Informaatioteoreettisen alarajan ja todellisen alarajan välinen vuorovaikutus muistuttaa paljon reaaliarvoista funktiota, joka laskee kokonaislukufunktiota. Tämä ei kuitenkaan pidä aivan paikkaansa, kun tarkastellaan keskimääräistä tapausta.
jotta saadaan selville, mitä tapahtuu, kun analysoidaan keskimääräistä tapausta, avain on se, että mihin “keskiarvo” viittaa? – Minkä keskiarvon? Jonkin verran tietoa informaatioteoriasta, informaatioteoreettinen alaraja keskiarvoja yli joukon kaikki permutaatiot kokonaisuutena. Mutta kaikki tietokonealgoritmit (alle, mitä uskotaan tällä hetkellä) on käsiteltävä kunkin permutation yksittäisenä esimerkkinä ongelma. Näin ollen keskimääräinen alaraja etsimme on keskiarvo kaikista yksittäisistä tapauksista.
etsiäksemme tietokoneiden saavuttamattomuuteen liittyvää alarajaa otamme käyttöön Päätöspuun mallin. Muotoilemme hieman uudelleen tavoitteemme. Ratkaisupuun mallissa esitetty alaraja on n: n juuresta lehteen suuntautuvien polkujen keskimääräisen pituuden alaraja ! {\displaystyle n!}
– lehtien binääripuu (jossa jokainen lehti vastaa permutaatiota). Se olisi vakuuttunut sanoa, että tasapainoinen koko binary puu saavuttaa minimi keskimääräinen pituus. Joitakin huolellisia laskelmia, sillä tasapainoinen täydellinen binary puu n ! {\displaystyle n!}
lehtiä, joiden tyvestä lehteen suuntautuvien polkujen keskipituus on annettu (2 n ! – 2 log log 2 n n ! ⌋ + 1) log log log 2 n n ! ⌉ + (2 log log 2 n n ! ⌋ + 1-n ! ) ⋅ log log 2 n n ! ⌋ n ! {\displaystyle {\frac {(2n!- 2^{\lfloor \log _ {2}n!\rfloor + 1})\cdot \lceil \log _ {2}n!\rceil +(2^{\lfloor \log _{2}n!\rfloor + 1} – n!) \cdot \lfloor \log _ {2}n!\rfloor } {n!}}}
esimerkiksi n = 3: lle informaatioteoreettinen alaraja keskimääräiselle tapaukselle on noin 2,58, kun taas keskimääräinen Päätöspuun mallin kautta johdettu alaraja on 8/3 eli noin 2,67.
jos useilla erillä voi olla sama avain, termille “keskimääräinen tapaus” ei ole selvää tilastollista tulkintaa, joten edellä mainitun kaltaista argumenttia ei voida soveltaa tekemättä erityisiä oletuksia avainten jakaumasta.
