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

Динамик массивдин башында же ортосунда элемент кошуу операциясынын убакытттык кыйынчылыгы адатта 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]
}