Kāda ir dinamiskā masīva elementa pievienošanas operācijas laika sarežģītība?

Dinamisks masīvs elementa pievienošana parasti ir ir amortizēta laika sarežģītība ir O(1).

Skaidrojums:

• Ja masīvā ir brīva vieta, elements tiek pievienots konstantā laikā.
• Ja vieta nav, masīvs piešķir jaunu, lielāku atmiņas bloku (parasti divreiz lielāku), kopē vecos elementus un pievieno jauno.

Lai gan paplašināšanas operācija aizņem O(n) laiku, tā notiek reti, tāpēc vidējā (amortizētā) pievienošanas sarežģītība paliek O(1).

Piemērs Go valodā ar slices:

var arr []int
arr = append(arr, 10) // elementa pievienošana

append automātiski paplašinās slices, ja tas ir nepieciešams.