Hogyan értékeljük egy elem törlésének időbeli összetettségét egy tömbből?

Egy elem törlésének időbeli komplexitása a tömb típusától és a törlés módjától függ:

• Egy standard tömbben (például, Array Swiftben) egy elem törlése index szerint a következő elemek balra tolását igényli, hogy kitöltse a "lyukat". Ez O(n) komplexitást eredményez, ahol n a törölt elem utáni elemek száma.

• Ha az utolsó elemet töröljük, az művelet általában O(1) idő alatt végrehajtható, mivel nincs szükség tolásra.

• Dinamikus tömbök esetén (például, ArrayList Java-ban vagy NSMutableArray Objective-C-ben) a helyzet hasonló — középről való törlés az elemek tolását igényli.

Példa:

var array = [1, 2, 3, 4, 5]
array.remove(at: 2) // törli a 2-es indexű elemet (szám 3)
// A törlés után a 4 és 5 elemek egy pozícióval balra tolódnak

Általánosságban elmondható, hogy egy elem törlése egy tömbből O(n) időkomplexitású művelet.