Rikiavimas suliejimu ir „skaldyk ir valdyk“ rekurentinė lygtis
Padalyti masyvą į dvi beveik lygias dalis, kiekvieną rekursyviai surikiuoti ir sulieti surikiuotas dalis, pakartotinai parenkant kitą raktą pagal rikiavimo tvarką.
Esminės žinios
Padalyti masyvą į dvi beveik lygias dalis, kiekvieną rekursyviai surikiuoti ir sulieti surikiuotas dalis, pakartotinai parenkant kitą raktą pagal rikiavimo tvarką. Suliejimo darbo apimtis yra Θ(n), todėl T(n)=T(⌊n/2⌋)+T(⌈n/2⌉)+Θ(n) duoda Θ(n log n) vykdymo laiką.
Sąlygos ir taikymo ribos
- Baziniuose atvejuose yra ne daugiau kaip vienas elementas; palyginimų ir masyvo operacijų sąnaudos yra aprėžtos.
- Įprastam masyvo suliejimui reikia Θ(n) papildomos atminties; ši garantija taikoma palyginimais grįstam rikiavimui.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Paskaitos 3 transkripto puslapiai 11–14: suliejimas naudojant dvi rodykles, rekursyvus dalijimas ir vykdymo laiko rekurentinė lygtis; dalių dydžių apvalinimas nurodytas aiškiai.
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-merge-sort
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra