Dinaminio masyvo talpos dvigubinimas
Pridėkite elementą į masyvo galą, jei jame yra laisvos vietos; masyvui užsipildžius, skirkite dvigubai didesnę talpą ir nukopijuokite esamus elementus.
Esminės žinios
Pridėkite elementą į masyvo galą, jei jame yra laisvos vietos; masyvui užsipildžius, skirkite dvigubai didesnę talpą ir nukopijuokite esamus elementus. Atliekant m pridėjimų, kopijuojamų elementų skaičiai sudaro geometrinę sumą O(m), todėl pridėjimo amortizuotosios sąnaudos yra O(1), nors pridėjimo, kuriam reikia pakeisti talpą, sąnaudos yra Θ(n).
Sąlygos ir taikymo ribos
- Pradėkite nuo teigiamos pastovios talpos; elementų perkėlimo sąnaudos turi būti aprėžtos, o atminties skyrimo sąnaudos – proporcingos skiriamos atminties ilgiui.
- Teiginys apima pridėjimą į galą, o ne įterpimą į bet kurią vietą, šalinimą ar netinkamai parinktą talpos mažinimo strategiją.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Paskaitos 11 skyrius 11.4: dinaminės lentelės plėtimas ir geometrine suma grindžiama suminė bei potencialo analizė.
2026-10-10 · Nepriklausoma AI redakcinė peržiūra: Perskaityti visi241 glausti teiginiai, prielaidos, pateiktos lygtys ir konvencijos bei visos596 iš šių įrašų išeinančios semantinės sąsajos; peržiūrėta visa autoriaus tikslių šaltinių patikros matrica, turinti241 įrašą, ir deklaruoti apribojimai. Siekiant aprėpti visą inventorių, perskaityti ankstesni105 faktiškai paveldėti matematikos ir informacijos įrašai. Toliau išvardyti tiksliniai nepriklausomai perskaityti pirminių šaltinių skyriai; tai NEREIŠKIA, kad nepriklausomai iš naujo perskaitytas kiekvienas cituotas šaltinio tekstas ar kiekvienas įrodymas. Tai AI atliekama informacinio turinio peržiūra, o ne žmogaus atliekamas dalykinis sertifikavimas, išsamus vadovėlio atkūrimas ar eksperimentų pakartojimas. Peržiūros dokumentas: mathematics-information-independent-content-review.1.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-dynamic-array-doubling
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra