Kokia yra dinaminio masyvo pradžioje arba viduryje elementų įterpimo operacijos laiko sudėtingumas?

Dinaminio masyvo pradžioje arba viduryje įterpiamo elemento laiko sudėtingumas paprastai yra O(n), kur n yra elementų skaičius masyve.

Tai susiję su tuo, kad po įterpimo visi vėlesni elementai turi būti perkelti viena pozicija į dešinę, kad būtų vietos naujam elementui. Blogiausiu atveju, įterpiant į pradžią, perkelti reikia visus elementus.

Pavyzdys Go kalba:

package main

import "fmt"

func insertAt(slice []int, index int, value int) []int {
    slice = append(slice, 0)           // padidiname skaidinį
    copy(slice[index+1:], slice[index:]) // perkelti elementus
    slice[index] = value               // įterpti reikšmę
    return slice
}

func main() {
    s := []int{1, 2, 3, 4}
    s = insertAt(s, 1, 99) // įterpti 99 pozicijoje 1
    fmt.Println(s)        // [1 99 2 3 4]
}