Pourquoi l'insertion à la fin d'un tableau dynamique O (1) lors de l'insertion au milieu est-elle O (n)?

Question

Conformément à l'article de Wikipedia sur les tableaux dynamiques , qui insère / supprime à la fin de la tableau est O (1) tandis que l'insertion / suppression à partir du milieu est O (n). Pourquoi est-ce exactement cela?

Aussi - si j'ai un tableau dynamique avec 5 éléments et que j'insère un nouvel élément en position 6, l'opération est O (n), alors que si j'utilise la fonction pour ajouter à la fin du tableau, il s'agit de O (1) . N'est-ce pas la même opération en supposant que le tableau n'a pas besoin d'être redimensionné dans les deux cas? Ou bien l’ajout au tableau dynamique insère-t-il vraiment le nouvel élément quelque part en plus de la position 6?

Merci!

MODIFIER: Je pense que ma principale confusion est la différence entre l'insertion à la fin du tableau et l'insertion à une position spécifique équivalente à la fin du tableau.

Je suppose qu’un pointeur sur l’adresse mémoire de la fin du tableau reste pratique, c’est pourquoi l’opération d’ajout est rapide. Inversement, si je spécifie une position précise (même s’il s’agit de la fin du tableau), il ne saura pas que l’insertion à cette position revient à utiliser l’adresse mémoire susmentionnée, elle doit donc parcourir l’ensemble du tableau, hein?

Answer 1

L'ordre de grandeur dépend entièrement de la sorte de structure de données du "tableau dynamique". c’est réellement (le "tableau dynamique" n’est pas une structure de données strictement définie, mais plutôt un résultat souhaité obtenu en utilisant une structure de données particulière). L'exemple que vous donnez serait celui qui est reflété par un tableau dynamique obtenu en utilisant une liste chaînée. O (1) peut être ajouté à la fin si la structure de la liste conserve un pointeur sur l'élément final. L’insertion (quel que soit l’index) nécessiterait de parcourir la liste chaînée, ce qui signifie une opération par noeud jusqu’à l’index souhaité.

Answer 2

Pour insérer à la fin d'un tableau, vous devez simplement y placer l'élément.

Pour insérer au milieu d'un tableau, vous devez déplacer les éléments après ce point d'une unité.

Pour supprimer de la fin d'un tableau, il vous suffit de supprimer son nombre d'une unité.

Pour supprimer du milieu, vous devez faire cela et décaler les autres éléments vers le bas.

C'est le décalage qui le transforme en O (n).

Answer 3

C'est assez simple:

L’insertion au milieu implique le déplacement de chaque élément ultérieur de 1. Pour insérer à la fin, s'il y a de l'espace supplémentaire réservé, l'élément est simplement stocké ici, mais s'il n'y a pas de nouvel espace alloué. Ainsi, cette opération est effectuée en temps constant amorti .

Answer 4

Ajoutant à l'excellent résumé d'Adam Robinson: il ne s'agit pas que de théorie. J'ai vu un certain nombre de situations dans lesquelles un tableau dynamique a été construit en ajoutant à plusieurs reprises à la fin du tableau. Cela donne lieu à des performances (N ** 2) , car le tableau doit être réaffecté à plusieurs reprises, ce qui oblige chacun de ses membres à être copié dans la nouvelle structure du tableau. Les réallocations ne peuvent se produire que sur 1/10 des opérations d’ajout, mais c’est déjà suffisant. (N ** 2) en termes de performances.

En LIST, cette pénalité de performances peut être évitée en appelant vector :: reserve (N) avant d'écrire dans le vecteur; mais cette étape est souvent négligée.

Answer 5

En réalité, il ne s’agit pas de Big-O mais de Big-Theta .