Indexation : Mécanisme permettant d'accéder à un élément d'une structure de données par son indice.
Accès direct : Accès à un élément en temps constant O(1) sans parcourir les éléments précédents.
- Identifier la structure de données (tableau, liste, etc.)
- Déterminer l'indice de l'élément souhaité
- Utiliser l'opérateur d'indexation [i] pour accéder à l'élément
- Vérifier que l'indice est valide (compris entre 0 et n-1)
Le tableau T contient 5 éléments : T[0]=10, T[1]=20, T[2]=30, T[3]=40, T[4]=50
Adresse(T[2]) = Adresse_base + 2 × taille_élément
Si la taille d'un entier est de 4 octets et que l'adresse de base est 1000 :
Adresse(T[2]) = 1000 + 2×4 = 1008
L'accès à T[2] se fait en O(1) car l'adresse est calculée directement
L'élément à l'indice 2 du tableau vaut 30. L'accès se fait en temps constant O(1).
• Indexation : Utiliser des indices entiers positifs ou nuls
• Accès direct : Temps constant indépendamment de la taille du tableau
• Sécurité : Vérifier que l'indice est dans les bornes du tableau
Recherche indexée : Accès à un élément spécifique via son indice connu.
Complexité : O(1) pour l'accès direct par rapport à O(n) pour une recherche linéaire.
Nous voulons accéder à l'élément à l'indice 3 du tableau Notes
Longueur du tableau = 5, donc indices valides : 0 à 4
L'indice 3 est valide car 0 ≤ 3 ≤ 4
Notes[3] correspond au 4ème élément du tableau (car l'indexation commence à 0)
Notes[0]=12, Notes[1]=15, Notes[2]=8, Notes[3]=17
L'élément à l'indice 3 du tableau Notes vaut 17. L'accès est immédiat en O(1).
• Indexation : Toujours vérifier que l'indice est dans les bornes du tableau
• Performance : L'accès direct est toujours en O(1), contrairement à la recherche linéaire en O(n)
• Erreur : Un indice hors limites provoque une erreur d'exécution
Adresse mémoire : Position exacte d'un élément dans la mémoire RAM.
Calcul d'adresse : Adresse(T[i]) = Adresse_base + i × taille_élément
- Adresse de base du tableau : 2000
- Taille d'un élément (entier) : 4 octets
- Indice recherché : 5
Adresse(T[i]) = Adresse_base + i × taille_élément
Adresse(T[5]) = 2000 + 5 × 4 = 2000 + 20 = 2020
L'élément T[5] est stocké à l'adresse mémoire 2020
Cette adresse est calculée en O(1), ce qui explique la rapidité de l'accès direct
| Indice | Adresse | Valeur |
|---|---|---|
| T[0] | 2000 | ? |
| T[1] | 2004 | ? |
| T[2] | 2008 | ? |
| T[3] | 2012 | ? |
| T[4] | 2016 | ? |
| T[5] | 2020 | ? |
| T[6] | 2024 | ? |
L'élément T[5] est situé à l'adresse mémoire 2020. Le calcul se fait en O(1).
• Calcul d'adresse : Adresse(T[i]) = Adresse_base + i × taille_élément
• Espace mémoire : Les éléments sont stockés de manière contiguë
• Performance : L'accès direct est possible grâce à ce calcul d'adresse
Modification directe : Changement de valeur d'un élément via son indice.
Opération : T[i] = nouvelle_valeur (encore en O(1))
Tableau T = [5, 10, 15, 20] avec T[0]=5, T[1]=10, T[2]=15, T[3]=20
Nous voulons modifier T[2] qui vaut actuellement 15
T[2] = 25 remplace la valeur 15 par 25
Le tableau devient : [5, 10, 25, 20]
La modification s'effectue en O(1) car l'adresse de T[2] est calculée directement
Après modification, T[2] vaut 25. La complexité de la modification est O(1).
• Modification : T[i] = nouvelle_valeur modifie l'élément en place
• Complexité : Les opérations de lecture et écriture sont toutes en O(1)
• Effet de bord : La modification affecte directement le tableau original
Structure de données : Organisation logique des données pour faciliter les opérations.
Tableau comme structure : Permet un accès direct aux éléments via leur indice.
Tableau Notes contenant 5 notes d'élèves : [12, 15, 8, 17, 14]
Pour calculer la moyenne, on accède à chaque élément via son indice
Somme = Notes[0] + Notes[1] + Notes[2] + Notes[3] + Notes[4]
Somme = 12 + 15 + 8 + 17 + 14 = 66
Moyenne = Somme / Nombre_d'éléments = 66 / 5 = 13.2
Pour n éléments, on effectue n accès directs O(1) → Complexité totale O(n)
Chaque accès individuel est en O(1) grâce à l'indexation
| Indice | Note | Accès |
|---|---|---|
| 0 | 12 | O(1) |
| 1 | 15 | O(1) |
| 2 | 8 | O(1) |
| 3 | 17 | O(1) |
| 4 | 14 | O(1) |
| Total | 66 | O(n) |
La moyenne des notes est de 13.2. L'utilisation de l'indexation permet des accès rapides O(1).
• Structure de données : Le tableau est optimal pour les accès par indice
• Accès direct : Chaque élément est accessible en O(1) grâce à l'indexation
• Applications : Recherche, tri, manipulation de données structurées
- Accès en lecture : valeur = tableau[indice]
- Accès en écriture : tableau[indice] = nouvelle_valeur
- Calcul d'adresse : base + (indice × taille_élément)
- Validation d'indices : 0 ≤ indice < longueur_tableau
- Parcours complet : Boucle de 0 à n-1 pour accéder à tous les éléments
- La complexité d'accès, de lecture et d'écriture est O(1)
- Les indices commencent à 0 et se terminent à n-1 pour un tableau de n éléments
- Un indice hors limites provoque une erreur d'exécution
- Les éléments sont stockés de manière contiguë en mémoire
- L'indexation est optimale pour les accès fréquents par position
- • L'indexation permet un accès direct aux éléments via leur indice
- • La complexité d'accès est constante O(1), ce qui est optimal
- • Les indices commencent à 0 et vont jusqu'à n-1 pour un tableau de n éléments
- • L'adresse mémoire est calculée par la formule : base + (indice × taille_élément)
- • L'indexation est particulièrement efficace pour les opérations de lecture/écriture
