See on masintõlge ja originaalartikkel on inglise keeles. Loe originaali
Miks sortimine ei saa muutuda kiiremaks
Saja elemendi sortimiseks on vaja vähemalt 525 võrdlust. Mitte tänapäevaste algoritmidega. Ega kunagi.
Enamik jõudlusalaseid väiteid on väited mõne konkreetse programmi kohta. See väide seda ei ole. See ütleb, et ükski võrdluspõhine sortimisalgoritm, mille on kirjutanud ükskõik kes, ükskõik millises keeles, ükskõik millisel veel leiutamata riistvaral, ei suuda sortida sadat elementi vähema kui 525 võrdlusega.
See arutlus ei vaatle kordagi algoritmi ennast.
Loenda sihtkohti, mitte samme
n eristatavast elemendist koosnevat loendit saab järjestada n! viisil. Täpselt üks neist on sorditud ning enne alustamist pole aimugi, milline neist teie käes on.
Mõelge nüüd sellele, mida võrdlus teile annab. Te küsite, kas a paikneb enne elementi b, ning saate vastuseks jah või ei. Üks bitt. Mida iganes teie algoritm edasi teeb, teeb ta seda teades ühe binaarse fakti võrra rohkem kui varem.
Nii et pärast c võrdlust olete saanud c bitti ning c bitti suudavad eristada maksimaalselt 2c erinevat olukorda. Et olla kindel, millisest n! järjestusest te alustasite, on vaja, et
2c ≥ n!, see tähendab, c ≥ log₂(n!).
See ongi kogu tõestus. See ei sisalda tsükleid, rekursiooni ega eeldusi strateegia kohta – mis on täpselt põhjus, miks see kehtib ka algoritmide kohta, mille peale keegi pole veel tulnud.
Selle üldtuntud nimetus on otsustuspuu tõke. Kujutlege mis tahes võrdlussortimist puuna: iga sisesõlm on võrdlus, iga haru on üks kahest vastusest ja iga leht on võimalik järjestus. Puul sügavusega c on maksimaalselt 2c lehte ning puul peab neid olema vähemalt n!, seega on selle sügavus vähemalt log₂(n!). Sügavus on võrdluste arv halvimal juhul.
Millised need arvud tegelikult on
Kahtteist elementi saab järjestada 479,001,600 viisil. Selle logaritm on 28,84, seega vajab kaksteist elementi vähemalt 29 võrdlust. Sada elementi vajab vähemalt 525. Miljon elementi vajab vähemalt 18,488,885.
Avage Big-O Complexity Explorer ja lugege rida, kus N = 100. Veerg O(N log N) näitab arvu 664, mis paikneb väärtuse 100 juures oleva O(N) ja väärtuse 10,000 juures oleva O(N²) vahel. See 664 on N × log₂N, kasvukiirus, mida nimetame sortimisel optimaalseks.
Kuid alumine piir on 525 ja 664 on sellest 26,6% kõrgem.
See erinevus ei tule tööriista ebatäpsusest. log₂(n!) ei ole täpselt n log₂ n: Stirlingi lähendus annab tulemuseks n log₂ n − 1,4427n ning kui N = 100, on selle paranduse väärtus 139 võrdlust. Nõnda väljendab "N log N" õiget kuju, kuid hindab tegelikku kulu üle sisendi suurusega proportsionaalse konstantse teguri võrra. See kuju on see, mis säilib N kasvades; 139 on see, mida te märksite, kui tõepoolest üle loendaksite.
Väljapääs, mis ei ole lünk
Loendussortimine sortib miljon väikest täisarvu palju vähema kui 18 miljoni tehtega ega räägi vähimalgi määral vastu ülaltoodule.
Tõestus eeldab, et iga teie küsitav küsimus on võrdlus. Loendussortimine küsib teistsugust küsimust: see loeb võtme ja kasutab seda aadressina. See eraldab korraga palju rohkem kui ühe biti, sest kasutab ära midagi, mida võrdlusmudel ei eelda – nimelt seda, et võtmed on väikesed täisarvud, mille sisse on lubatud vaadata.
See on kasulik harjumus. Alumine tõke on alati alumine tõke teatud mudeli piires ning kui näib, et tulemusest on jagu saadud, muudeti mudelit. Tööriist Sorting Race paneb võrdluspõhised algoritmid omavahel võistlema ning neid eristavad konstantkordajad ja käitumine mälus, mitte astendaja. Nad kõik on alt tõkestatud sama arvuga 525.
Kus te olete sellega varem kokku puutunud
Kui loendamissamm tundub tuttav, on see sama mõte selle taga, miks ükski tihendusprogramm ei saa kõiki faile tihendada. Seal loendati võimalikke faile võimalike lühemate failide vastu; siin aga võimalikke järjestusi võimalike vastusejärjestuste vastu. Mõlemad tõestused toimivad, märgates, et tulemuste hulk on suurem kui hulk asju, mis saaksid neid kirjeldada.
Entropy Coding on sama suurus teisest suunast: tegelikult vajamineva bittide arvu määrab ära see, kui palju võimalusi on järele jäänud, ning ükski kodeering ei ületa seda.
Kumbki tulemus ei õpeta teile, kuidas kirjutada kiiret programmi. Need ütlevad teile, millal lõpetada selle otsimine.