Dinamik massivdə elementləri əvvəlinə və ya ortasına əlavə etmə əməliyyatının vaxt mürəkkəbliyi nədir?

Dinamik bir massivdə elementin başlanğıca və ya ortasına əlavə əməliyyatının vaxt mürəkkəbliyi adətən O(n) təşkil edir, burada n massivdəki elementlərin sayıdır.

Bu, əlavə etdikdən sonra bütün sonrakı elementlərin sağa doğru hərəkət etdirilməsini tələb etdiyi üçün baş verir, yeni element üçün yer açmaq üçün. Ən pis halda, başlanğıca əlavə etdikdə, bütün elementlər hərəkət etdirilir.

Go dilində nümunə:

package main

import "fmt"

func insertAt(slice []int, index int, value int) []int {
    slice = append(slice, 0)           // dilimi genişləndiririk
    copy(slice[index+1:], slice[index:]) // elementləri hərəkət etdiririk
    slice[index] = value               // dəyəri əlavə edirik
    return slice
}

func main() {
    s := []int{1, 2, 3, 4}
    s = insertAt(s, 1, 99) // 99-u 1-ci mövqeyə əlavə et
    fmt.Println(s)        // [1 99 2 3 4]
}