Wie ist die zeitliche Komplexität der Operation zum Einfügen von Elementen am Anfang oder in der Mitte eines dynamischen Arrays?

Die zeitliche Komplexität der Operation zum Einfügen eines Elements am Anfang oder in der Mitte eines dynamischen Arrays beträgt in der Regel O(n), wobei n die Anzahl der Elemente im Array ist.

Dies liegt daran, dass nach dem Einfügen alle nachfolgenden Elemente um eine Position nach rechts verschoben werden müssen, um Platz für das neue Element zu schaffen. Im schlimmsten Fall, beim Einfügen am Anfang, werden alle Elemente verschoben.

Beispiel in Go:

package main

import "fmt"

func insertAt(slice []int, index int, value int) []int {
    slice = append(slice, 0)           // Array vergrößern
    copy(slice[index+1:], slice[index:]) // Elemente verschieben
    slice[index] = value               // Wert einfügen
    return slice
}

func main() {
    s := []int{1, 2, 3, 4}
    s = insertAt(s, 1, 99) // Einfügen von 99 an Position 1
    fmt.Println(s)        // [1 99 2 3 4]
}