Динамикалық массивке элементтерді бастапқыда немесе ортасында қосу операциясының уақыттық күрделілігі қандай?

Динамикалық массивке элементті бастапқыға немесе ортасына енгізу операциясының уақыттық күрделілігі әдетте O(n) құрайды, мұнда n — массивтегі элементтердің саны.

Бұл, себебі енгізгеннен кейін барлық кейінгі элементтерді бір орынға оңға жылжыту керек, жаңа элемент үшін орын босату үшін. Ең нашар жағдайда, бастапқыға енгізгенде, барлық элементтер жылжиды.

Go тілінде мысал:

package main

import "fmt"

func insertAt(slice []int, index int, value int) []int {
    slice = append(slice, 0)           // кескінді кеңейтеміз
    copy(slice[index+1:], slice[index:]) // элементтерді жылжытамыз
    slice[index] = value               // мәнді енгіземіз
    return slice
}

func main() {
    s := []int{1, 2, 3, 4}
    s = insertAt(s, 1, 99) // 99-ды 1-ші орынға енгізу
    fmt.Println(s)        // [1 99 2 3 4]
}