Ποια είναι η χρονική πολυπλοκότητα της λειτουργίας εισαγωγής στοιχείων στην αρχή ή στη μέση ενός δυναμικού πίνακα;

Η χρονική πολυπλοκότητα της λειτουργίας εισαγωγής ενός στοιχείου στην αρχή ή στο μέσο ενός δυναμικού πίνακα είναι συνήθως O(n), όπου n είναι ο αριθμός των στοιχείων στον πίνακα.

Αυτό οφείλεται στο γεγονός ότι μετά την εισαγωγή, όλα τα επόμενα στοιχεία πρέπει να μετακινηθούν μία θέση προς τα δεξιά για να δημιουργηθεί χώρος για το νέο στοιχείο. Στην χειρότερη περίπτωση, κατά την εισαγωγή στην αρχή, μετακινούνται όλα τα στοιχεία.

Παράδειγμα σε Go:

package main

import "fmt"

func insertAt(slice []int, index int, value int) []int {
    slice = append(slice, 0)           // αυξάνουμε το slice
    copy(slice[index+1:], slice[index:]) // μετακινούμε τα στοιχεία
    slice[index] = value               // εισάγουμε την τιμή
    return slice
}

func main() {
    s := []int{1, 2, 3, 4}
    s = insertAt(s, 1, 99) // εισαγωγή 99 στη θέση 1
    fmt.Println(s)        // [1 99 2 3 4]
}