Kokia yra dinaminio masyvo elemento pridėjimo operacijos laiko sudėtingumas?

Dinaminio masyvo elemento pridėjimas paprastai turi amortizuotą laiką sudėtingumą O(1).

Paaiškinimas:

• Jei masyve yra laisvos vietos, elementas pridedamas per pastovų laiką.
• Jei vietos nėra, masyvas paskiria naują didesnį atminties bloką (dažniausiai dvigubai didesnį), kopijuoja senus elementus ir prideda naują.

Nors plėtros operacija užima O(n) laiką, ji vyksta retai, todėl vidutinė (amortizuota) pridėjimo sudėtingumas lieka O(1).

Pavyzdys Go kalboje su slices:

var arr []int
arr = append(arr, 10) // elementų pridėjimas

append automatiškai išplės slices, jei reikės.