Pourquoi l'accès à un élément d'un tableau prend-il un temps constant ?

Question

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).

Answer 1

Un tableau est une collection de types de données similaires. Par conséquent, si vous connaissez l'adresse de base du tableau et le type de données qu'il contient, vous pouvez facilement obtenir l'élément Array[i] en un temps constant en utilisant la formule ci-dessous :

int takes 4 bytes in a 32 bit system.
int array[10];
base address=4000;
location of 7th element:4000+7*4.
array[7]=array[4000+7*4];

Il est donc évident que vous pouvez obtenir le ième élément en un temps constant si vous connaissez l'adresse de base et le type de données qu'elle contient. Veuillez visiter este pour en savoir plus sur la structure de données des tableaux.

Answer 2

Un tableau est séquentiel, ce qui signifie que l'adresse de l'élément suivant dans le tableau est la suivante de celle de l'élément actuel. Ainsi, si vous voulez obtenir le 5e élément d'un tableau, vous calculez l'adresse du 5e élément en additionnant l'adresse de base du tableau avec 5. Cette adresse directe est maintenant utilisée directement pour obtenir l'élément à cette adresse.

Vous pouvez maintenant vous poser la même question ici : "Comment l'ordinateur connaît-il/accède-t-il directement à l'adresse calculée ?" C'est la nature et le principe de la mémoire de l'ordinateur (RAM). Si vous souhaitez en savoir plus sur la façon dont la RAM accède à n'importe quelle adresse en temps constant, vous pouvez le trouver dans n'importe quel texte sur l'organisation des ordinateurs ou vous pouvez simplement le chercher sur Google.

Answer 3

Si nous connaissons l'emplacement de la mémoire auquel il faut accéder, cet accès se fait en temps constant. Dans le cas d'un tableau, l'emplacement de la mémoire est calculé en utilisant le pointeur de base, l'index de l'élément et la taille de l'élément. Cela implique des opérations de multiplication et d'addition qui prennent un temps constant pour être exécutées. Par conséquent, l'accès à l'élément dans le tableau prend un temps constant.