Quel est le résultat temporel des opérations d'insertion, de recherche, de lecture et de suppression d'éléments dans un tableau dans les cas pires et moyens?

Pour un tableau standard sur iOS (par exemple, NSArray ou NSMutableArray), les caractéristiques temporaires des opérations sont approximativement les suivantes :

• Insertion :

  • À la fin du tableau (append) : cas moyen et pire — O(1) amorti (si aucune redistribution de mémoire n'est nécessaire).
  • Au début ou au milieu : O(n), car il faut décaler les éléments.

• Recherche (si par index) : O(1), car le tableau est indexé.

• Lecture par index : O(1).

• Suppression :

  • Depuis la fin du tableau : O(1).
  • Depuis le début ou le milieu : O(n), en raison du décalage des éléments.

Ainsi, les opérations d'insertion et de suppression au début ou au milieu du tableau ont une complexité linéaire, tandis que l'accès et l'insertion/suppression à la fin sont constantes (amorties).