Ang mga diynamic array ay mga data structure na awtomatikong nagreresulta kapag naabot nila ang kapasidad. Ang pag-unawa sa kanilang amortisadong halaga ay tumutulong sa pagsuri ng kanilang kahusayan sa maramihang mga operasyon.

Ano ba ang Amortized Cost?

Ang kabayarang amortized ay ang katamtamang halaga sa bawat operasyon sa pamamagitan ng sunud - sunod na operasyon.Pinagaan nito ang mataas na halaga ng paminsan - minsang muling pag - aayos sa pamamagitan ng pamamahagi nito sa maraming murang operasyon.

Dinamikong mga Operasyong Array

Ang mga karaniwang operasyon sa mga dinamikong array ay kinabibilangan ng pagpapasok, deleksiyon, at muling pag-iinsperimento. Ang insersyon sa dulo ay karaniwang ang pinakamadalas na operasyon, na maaaring mag-udyok ng muling pag-eensayo kapag ang kapasidad ay nahigitan.

Pagtaya sa Halaga ng Amortized

Kapag nagpapasok ng mga elemento, ang array ay nadodoble ang laki kapag buo na. Ang halaga ng muling pag-eeensayo ay kinasasangkutan ng pagkopya ng lahat ng umiiral na elemento sa bagong hanay. bagaman ang muling pag-eeeksperimento ay magastos, ito ay bihirang nangyayari.

Halimbawa, kung ang isang array ay magsimula sa kapasidad 1, ang pagkakasunud - sunod ng mga halaga na muling ginagamit sa maramihang pagpapasok ay maaaring buuin bilang:

  • Nakasingit na 1 elemento: halaga 1
  • Inuuri ang 2nd elemento: resize (cost 1), kabuuang halaga 2
  • Inunsyo 3rd elemento: resize (cost 2), kabuuang halaga 3
  • Inuuring 4th elemento: resize (cost 4), kabuuang halaga 4

Ang kabuuang halaga sa mga n instansiya ay proporsiyonal hanggang 2n, na ginagawa ang amortisadong halaga sa bawat inkorsyon humigit-kumulang O(1).