Skaitmeninis rikiavimas nuo mažiausiai reikšminio skaitmens
Neneigiamus sveikuosius raktus išreikškite d skaitmenų B pagrindo sistemoje ir stabiliai rikiuokite pagal kiekvieną skaitmenį nuo mažiausiai iki labiausiai reikšminio.
Esminės žinios
Neneigiamus sveikuosius raktus išreikškite d skaitmenų B pagrindo sistemoje ir stabiliai rikiuokite pagal kiekvieną skaitmenį nuo mažiausiai iki labiausiai reikšminio. Po kiekvieno perėjimo apdorota skaitmenų priesaga yra surikiuota, todėl, perėjimams naudojant rikiavimą skaičiavimu, bendras laikas yra O(d(n+B)). Pasirinkus B=n, raktai, apriboti nᶜ, surikiuojami per tiesinį laiką, kai c yra fiksuotas.
Sąlygos ir taikymo ribos
- n≥2, B≥2; nurodytame mašininio žodžio modelyje skaitmens išskyrimo ir indeksavimo sąnaudos yra vienetinės.
- Kiekvienas rikiavimo pagal skaitmenį perėjimas turi būti stabilus; neribotas bitų skaičius didina d ir faktines bitinių operacijų sąnaudas.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
5 paskaita „Kortežų rikiavimas ir skaitmeninis rikiavimas“, spausdinto leidinio p. 3–4; sąnaudos bendruoju pagrindo atveju nustatomos skaičiuojant tuos pačius perėjimus per kibirėlius.
2026-10-10 · Nepriklausoma DI redakcinė peržiūra: perskaityti visi glaustai suformuluoti teiginiai (241), hipotezės, pateiktos lygtys ir susitarimai bei visos kilmės semantinės sąsajos (596); peržiūrėta visa autoriaus sudaryta 241 įrašo tikslių šaltinių patikros matrica ir deklaruoti apribojimai. Siekiant aprėpti visą įrašų rinkinį, perskaityti 105 ankstesni faktiškai paveldėti matematikos ir informacijos įrašai. Toliau išvardyti tikslingai ir nepriklausomai peržiūrėti pirminių šaltinių skyriai; tuo NETEIGIAMA, kad kiekvieno cituojamo šaltinio visas tekstas ar kiekvienas įrodymas buvo nepriklausomai perskaitytas iš naujo. Tai DI atlikta informacinio turinio peržiūra, o ne žmogaus eksperto patvirtinimas atitinkamoje mokslo srityje, išsamus vadovėlio atkūrimas ar eksperimentinis pakartojimas. Peržiūros įrašas: mathematics-information-independent-content-review.1.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-lsd-radix-sort
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra