Riba, kurios neaplenki — o apeini

Pirmoje pamokoje parašei Item ir du jo laukus apribojai:

const (
	MinYear   = 1900
	MaxYear   = 2030
	MinRating = 0
	MaxRating = 100
)

Tada tekste buvo pasakyta: „Todėl šie du laukai turi rėžius jau dabar, aštuoniomis pamokomis anksčiau, negu jų prireiks."

Ši pamoka yra tie aštuoni. Štai kam tie du apriboti laukai buvo reikalingi — tai jų pačių atsipirkimas, atskiras nuo -sorted, kurią septinta ir aštunta jau panaudojo ir su kuria dar ne viskas baigta.

Spėk prieš skaitydamas toliau

Aštuntoje pamokoje suliejimo rikiavimas 100 000 įrašų atliko apie 1,7 milijono palyginimų. Septintoje įterpimo — 2,5 milijardo.

Kiek mažiausiai palyginimų gali atlikti rikiavimas ir vis tiek būti teisingas?

Užsirašyk skaičių. Beveik neabejotinai jis bus per didelis.

Kodėl palyginimų riba egzistuoja

Rikiavimas palyginimais yra sprendimų medis: kiekvienas palyginimas duoda vieną bitą — „taip" arba „ne" — ir tų bitų reikia tiek, kad atskirtum visas įmanomas pradines tvarkas.

n elementų turi n! galimų tvarkų. Kad atskirtum vieną iš n!, reikia bent log₂(n!) dvejetainių sprendimų, o log₂(n!) ≈ n log₂ n.

Iš čia ir Ω(n log n): joks rikiavimas, kuris sprendžia lygindamas, negali greičiau. Suliejimo rikiavimas šią ribą pasiekia — jis optimalus savo klasėje.

Ir kodėl šios pamokos algoritmai jos nelaužo

Jie tos ribos neaplenkia. Jie iš jos išeina.

Riba kalba apie algoritmus, kurie sprendžia lygindami elementus tarpusavyje. Šios pamokos algoritmai to nedaro nė karto. Jie neklausia „ar A prieš B?" — jie ima raktą ir tiesiog paskaičiuoja, kiek kartų kiekviena reikšmė pasitaiko.

Ω(n log n) galioja rikiavimams palyginimais. Nustok lyginti — ir riba nustoja galioti tau.

Tai ne gudrybė ir ne skylė teorijoje. Tai kita prielaidų aibė, ir už ją reikia sumokėti — kaina bus 5 žingsnyje.