Kaip įvertinti elemento ištrynimo iš masyvo operacijos laiko sudėtingumą?

Elemento ištrynimo iš masyvo laiko sudėtingumas priklauso nuo masyvo tipo ir ištrynimo metodo:

• Standartiniame masyve (pavyzdžiui, Array Swift) elemento ištrynimas pagal indeksą reikalauja visų vėlesnių elementų perkelimo į kairę, kad užpildytų "skylę". Tai lemia O(n) sudėtingumą, kur n yra po ištrynimo esantys elementai.

• Jei ištrinamas paskutinis elementas, operacija dažniausiai atliekama per O(1), nes perkėlimas nereikalingas.

• Dinamiškuose masyvuose (pavyzdžiui, ArrayList Java arba NSMutableArray Objective-C) situacija panaši — viduryje ištrynus elementą, reikalingas elementų perkėlimas.

Pavyzdys:

var array = [1, 2, 3, 4, 5]
array.remove(at: 2) // ištrina elementą indeksu 2 (skaičius 3)
// Po ištrynimo, elementai 4 ir 5 persikelia vieną poziciją į kairę

Apskritai, ištrinti elementą iš masyvo yra operacija su laiko sudėtingumu O(n).