¿Por qué el acceso a un elemento en una matriz lleva un tiempo constante?

Digamos que tengo una matriz como:

int a[]={4,5,7,10,2,3,6}

cuando accedo a un elemento, como a[3], ¿qué sucede realmente detrás de escena? ¿Por qué muchos libros de algoritmos (como el libro de Cormen…) dicen que lleva un tiempo constante?

(Solo soy un novato en programación de bajo nivel, así que me gustaría aprender más de ustedes)

La matriz, efectivamente, se conoce por una ubicación de memoria (un puntero). Accediendo a[3] se puede encontrar en tiempo constante, ya que es solo ubicación_de_a+3*tamaño(int).

En C, puedes ver esto directamente. Recuerda, a[3] es lo mismo que *(a+3) – que es un poco más claro en términos de lo que está haciendo (desreferenciando el puntero “3 elementos”).

una matriz de 10 variables enteras, con índices del 0 al 9, puede almacenarse como 10 palabras en las direcciones de memoria 2000, 2004, 2008, … 2036, de modo que el elemento con índice i tenga la dirección 2000 + 4 × i. este proceso toma una multiplicación y una suma. Dado que estas dos operaciones toman un tiempo constante, podemos decir que el acceso se puede realizar en un tiempo constante.

Solo para ser completo, “¿a qué estructura se accede en tiempo lineal?” A Lista enlazada Se accede a la estructura en tiempo lineal. Para obtener el n elemento por el que tienes que viajar n-1 elementos anteriores. Ya sabes, como una grabadora o un casete VHS, donde ir al final de la cinta/VHS tenías que esperar mucho tiempo 🙂

Una matriz es más similar a un disco duro: cada punto es accesible en tiempo “constante” 🙂

Esta es la razón por la cual la memoria RAM de una computadora se llama RAM: memoria de acceso aleatorio. Puede ir a cualquier ubicación si conoce su dirección sin atravesar toda la memoria antes de esa ubicación.

Algunas personas me dijeron que el acceso a la HD no es realmente en tiempo constante (donde por acceso me refiero a “tiempo para colocar la cabeza y leer un sector de la HD”). Tengo que decir que no estoy seguro de ello. He buscado en Google y no he encontrado a nadie que hable de ello. SÍ sé que el tiempo no es lineal, porque todavía se accede al azar. Al final, si cree que el acceso a HD no es lo suficientemente constante para usted (pero entonces, ¿qué es constante? ¿El acceso a la RAM? ¿Teniendo en cuenta las optimizaciones de Caché, Precarga, Localidad de datos y Compilador?), Siéntase libre de considerar la oración como Una matriz es más similar a una memoria USB: se puede acceder a cada punto en un tiempo “constante” 🙂

Porque las matrices se almacenan en la memoria secuencialmente. Entonces, en realidad, cuando accedes a la matriz[3] le está diciendo a la computadora: “Obtenga la dirección de memoria del comienzo de la matriz, luego agregue 3 y luego acceda a ese lugar”. Dado que agregar toma un tiempo constante, ¡también lo hace el acceso a la matriz!

“tiempo constante” realmente significa “tiempo que no depende del ‘tamaño del problema'”. Para el ‘problema’ “sacar algo de un contenedor”, el ‘tamaño del problema’ es el tamaño del contenedor.

Acceder a un elemento de matriz lleva básicamente la misma cantidad de tiempo (esto es una simplificación) independientemente del tamaño del contenedor, porque se utiliza un conjunto fijo de pasos para recuperar el elemento: se calcula su ubicación en la memoria (esto también es una simplificación), y luego se recupera el valor en esa ubicación en la memoria.

Una lista enlazada, por ejemplo, no puede hacer esto, porque cada enlace indica la ubicación del siguiente. Para encontrar un elemento tienes que trabajar con todos los anteriores; en promedio, trabajará con la mitad del contenedor, por lo que el tamaño del contenedor obviamente importa.

Array es una colección de tipos similares de datos. Entonces, todos los elementos ocuparán la misma cantidad de memoria. Por lo tanto, si conoce la dirección base de la matriz y el tipo de datos que contiene, puede obtener fácilmente la matriz de elementos[i] en tiempo constante utilizando la fórmula que se indica a continuación:

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];

Por lo tanto, es claramente visible que puede obtener un elemento en un tiempo constante si conoce la dirección base y el tipo de datos que contiene. Por favor visita este enlace para saber más sobre la estructura de datos de matriz.

Una matriz es secuencial, lo que significa que la dirección del siguiente elemento en la matriz está junto a la actual. Entonces, si desea obtener el quinto elemento de una matriz, calcule la dirección del quinto elemento sumando la dirección base de la matriz con 5. Esta dirección directa ahora se usa directamente para obtener el elemento en esa dirección.

Ahora puede hacer la misma pregunta aquí: “¿Cómo sabe/accede la computadora a la dirección calculada directamente?” Esta es la naturaleza y el principio de la memoria de computadora (RAM). Si está más interesado en cómo la RAM accede a cualquier dirección en tiempo constante, puede encontrarlo en cualquier texto de organización de computadora o simplemente puede buscarlo en Google.