Kāda ir dinamiskā masīva elementu ievietošanas operācijas laika sarežģītība sākumā vai vidū?

Dinamiskā masīva sākuma vai vidus elementa ievietošanas operācijas laika sarežģītība parasti ir O(n), kur n ir elementu skaits masīvā.

Tas ir tāpēc, ka pēc ievietošanas visi sekojošie elementi ir jānovieto pa labi par vienu pozīciju, lai atbrīvotu vietu jaunajam elementam. Sliktākajā gadījumā, ievietojot sākumā, tiek pārvietoti visi elementi.

Piemērs Go valodā:

package main

import "fmt"

func insertAt(slice []int, index int, value int) []int {
    slice = append(slice, 0)           // palielinām sagriezienu
    copy(slice[index+1:], slice[index:]) // pārvietojam elementus
    slice[index] = value               // ievietojam vērtību
    return slice
}

func main() {
    s := []int{1, 2, 3, 4}
    s = insertAt(s, 1, 99) // ievietot 99 pozīcijā 1
    fmt.Println(s)        // [1 99 2 3 4]
}