რა არის დინამიური მასივის დასაწყისში ან შუაში ელემენტების ჩაწერის ოპერაციის დროითი სირთულე?

დინამიური მასივის დასაწყისში ან შუაში ელემენტის ჩასმა ოპერაციის დროის სირთულე ჩვეულებრივ არის 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]
}