Kā novērtēt elementa dzēšanas no masīva operācijas laika sarežģītību?

Laika sarežģītība elementa dzēšanai no masīva ir atkarīga no masīva veida un dzēšanas metodes:

• Standarta masīvā (piemēram, Array Swift) elementa dzēšana pēc indeksa prasa visu sekojošo elementu pārvietošanu pa kreisi, lai aizpildītu "caurumu". Tas noved pie O(n) sarežģītības, kur n ir elementu skaits pēc dzēšamā.

• Ja tiek dzēsts pēdējais elements, operācija parasti tiek veikta O(1) laikā, jo pārvietošana nav nepieciešama.

• Dinamiskiem masīviem (piemēram, ArrayList Java vai NSMutableArray Objective-C) situācija ir līdzīga — vidējā daļa prasa elementu pārvietošanu.

Piemērs:

var array = [1, 2, 3, 4, 5]
array.remove(at: 2) // dzēš elementu ar indeksu 2 (skaitlis 3)
// Pēc dzēšanas elementi 4 un 5 tiek pārvietoti par vienu pozīciju pa kreisi

Kopumā, elementa dzēšana no masīva ir operācija ar laika sarežģītību O(n).