Disons que j'ai un tableau comme :
int a[]={4,5,7,10,2,3,6}
lorsque j'accède à un élément, tel que a[3] mais que se passe-t-il réellement dans les coulisses ? Pourquoi de nombreux livres sur les algorithmes (comme le livre de Cormen...) disent-ils que cela prend un temps constant ?
(Je ne suis qu'un novice en matière de programmation de bas niveau et j'aimerais que vous m'en appreniez davantage).
Le tableau, en fait, est connu par un emplacement mémoire (un pointeur). Accès à a[3] peut être trouvé en temps constant, puisque c'est juste location_of_a+3*sizeof(int).
En C, vous pouvez voir cela directement. Rappelez-vous, a[3] est la même chose que *(a+3) - qui est un peu plus clair en termes de ce qu'il fait (déréférencer le pointeur "3 items" plus).
Un tableau de 10 variables entières, avec des indices de 0 à 9, peut être stocké sous forme de 10 mots aux adresses mémoire 2000, 2004, 2008, 2036, de sorte que l'élément avec l'indice i a l'adresse 2000 + 4 × i. Ce processus nécessite une multiplication et une addition, car ces deux opérations sont effectuées en temps constant.
Pour être complet, "quelle structure est accessible en temps linéaire ?" A Liste liée est accessible en temps linéaire. Pour obtenir le n élément que vous devez traverser n-1 les éléments précédents. Vous savez, comme un magnétophone ou une cassette VHS, où pour aller à la fin de la bande/VHS il fallait attendre longtemps :-)
Un tableau est plus similaire à un disque dur : chaque point est accessible en temps "constant" :-)
C'est la raison pour laquelle la mémoire vive d'un ordinateur est appelée RAM : Random Access Memory. Vous pouvez aller à n'importe quel endroit si vous connaissez son adresse sans traverser toute la mémoire avant cet endroit.
Certaines personnes m'ont dit que l'accès au disque dur n'est pas vraiment en temps constant (par accès, j'entends "le temps de positionner la tête et de lire un secteur du disque dur"). Je dois dire que je n'en suis pas sûr. J'ai fait des recherches sur Google et je n'ai trouvé personne qui en parle. Je sais que le temps n'est pas linéaire, car l'accès est toujours aléatoire. En fin de compte, si vous pensez que l'accès au disque dur n'est pas assez constant pour vous (mais alors, qu'est-ce qui est constant ? l'accès de la RAM ? en considérant le cache, le préfixe, la localité des données et les optimisations du compilateur), vous pouvez considérer la phrase comme suit Un tableau est plus similaire à une clé USB : chaque point est accessible en temps "constant" :-)
Parce que les tableaux sont stockés en mémoire de manière séquentielle. Donc, en réalité, lorsque vous accédez à array[3], vous dites à l'ordinateur : "Obtenez l'adresse mémoire du début du tableau, puis ajoutez 3, puis accédez à cet endroit". Puisque l'addition prend un temps constant, il en va de même pour l'accès au tableau !
"temps constant" signifie en réalité "temps qui ne dépend pas de la "taille du problème"". Pour le "problème" "sortir quelque chose d'un récipient", la "taille du problème" est la taille du récipient.
L'accès à un élément de tableau prend fondamentalement le même temps (il s'agit d'une simplification) quelle que soit la taille du conteneur, car un ensemble fixe d'étapes est utilisé pour récupérer l'élément : son emplacement en mémoire (il s'agit également d'une simplification) est calculé, puis la valeur à cet emplacement en mémoire est récupérée.
Une liste chaînée, par exemple, ne peut pas le faire, car chaque lien indique l'emplacement du suivant. Pour trouver un élément, vous devez passer par tous les éléments précédents ; en moyenne, vous passerez par la moitié du conteneur, donc la taille du conteneur est évidemment importante.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
