Hogyan határozható meg egy slice típusú tömb elemének törlésének időbeli összetettsége?

Go-ban a slice egy olyan szerkezet, amely egy mutatót tartalmaz egy tömbre, egy hosszúságot és egy kapacitást. Egy elem törlésekor a slice-ból általában szükséges az összes következő elemet egy pozícióval balra mozgatni, hogy kitöltse a "lyukat".

Ennek az műveletnek az időbeli komplexitása O(n), ahol n a törölt elem utáni elemek száma. Ez azért van, mert (n - törölt_index - 1) elemet kell másolni.

Elem törlése index szerint példával:

func remove(slice []int, i int) []int {
    return append(slice[:i], slice[i+1:]...)
}

Itt az append másolja a slice[i+1:] elemeket a slice[:i] utáni pozícióba, ami lineáris időt igényel a másolt elemek számától függően.