Dinamik massivning boshiga yoki o'rtasiga elementlar qo'shish operatsiyasining vaqt murakkabligi qanday?

Dinamik massivning boshiga yoki o'rtasiga element qo'shish operatsiyasining vaqt murakkabligi odatda O(n), bu yerda n massivdagi elementlar sonidir.

Bu shundan iboratki, qo'shishdan so'ng, keyingi barcha elementlarni o'ngga siljitish kerak, yangi element uchun joy bo'shatish uchun. Eng yomon holatda, boshiga qo'shilganda, barcha elementlar siljiydi.

Go tilida misol:

package main

import "fmt"

func insertAt(slice []int, index int, value int) []int {
    slice = append(slice, 0)           // slice ni kengaytiramiz
    copy(slice[index+1:], slice[index:]) // elementlarni siljitamiz
    slice[index] = value               // qiymatni qo'shamiz
    return slice
}

func main() {
    s := []int{1, 2, 3, 4}
    s = insertAt(s, 1, 99) // 99 ni 1-pozitsiyaga qo'shish
    fmt.Println(s)        // [1 99 2 3 4]
}