Quelle est la complexité temporelle de l'opération d'insertion d'éléments au début ou au milieu d'un tableau dynamique?

La complexité temporelle de l'opération d'insertion d'un élément au début ou au milieu d'un tableau dynamique est généralement de O(n), où n est le nombre d'éléments dans le tableau.

Cela est dû au fait qu'après l'insertion, tous les éléments suivants doivent être décalés d'une position vers la droite pour faire de la place pour le nouvel élément. Dans le pire des cas, lors de l'insertion au début, tous les éléments sont décalés.

Exemple en Go:

package main

import "fmt"

func insertAt(slice []int, index int, value int) []int {
    slice = append(slice, 0)           // augmenter la taille du slice
    copy(slice[index+1:], slice[index:]) // décaler les éléments
    slice[index] = value               // insérer la valeur
    return slice
}

func main() {
    s := []int{1, 2, 3, 4}
    s = insertAt(s, 1, 99) // insérer 99 à la position 1
    fmt.Println(s)        // [1 99 2 3 4]
}