Digamos que tengo una matriz como:¿por qué el acceso a un elemento en una matriz lleva tiempo constante?
int a [] = {} 4,5,7,10,2,3,6
cuando accedo a un elemento, tal como un [3] , ¿qué sucede realmente detrás de la escena? ¿Por qué muchos libros de algoritmos (como el libro de Cormen ...) dicen que lleva un tiempo constante?
(Sólo soy un novato en la programación de bajo nivel por lo que me gustaría aprender más de ustedes)
Para completar, ¿a qué estructura se accede en tiempo lineal? Se accede a una estructura Linked List en tiempo lineal. Para obtener el elemento n tiene que viajar a través de n-1 elementos anteriores. Ya sabes, como una grabadora o un casete VHS, dónde 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 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 HD no es realmente en tiempo constante (donde por acceso quiero decir "tiempo para colocar la cabeza y leer un sector de la HD"). Debo decir que no estoy seguro de eso. He buscado en Google y no he encontrado a nadie hablando de eso. SÍ, sé que el tiempo no es lineal, porque todavía se accede aleatoriamente. Al final, si crees que el acceso HD no es lo suficientemente constante para ti (pero entonces, ¿qué es constante? El acceso de la memoria RAM? Teniendo en cuenta la caché, la captura previa, la localización de datos y las optimizaciones del compilador?), Puedes considerar la oración como Una matriz es más similar a una unidad de disco USB: cada punto es accesible en tiempo "constante" :-)
Los discos duros son un mal ejemplo para una memoria de acceso aleatorio, porque eso es exactamente lo que no son. ¿Tal vez usar una memoria USB o un disco de estado sólido como ejemplo? – blubb
Sí y no ... Técnicamente, la parte "externa" de una HD es más rápida que la parte interna, pero ignoraremos esto. El acceso a un archivo en HD se realiza en tiempo constante (o al menos no en tiempo lineal). Si tiene un archivo en HD o un millón de archivos en HD, acceder a uno de ellos tomará el mismo tiempo (no exactamente, pero es más un modelo teórico que la realidad física en la que vivimos :-)). – xanatos
¿Se puede explicar el -1? Lo repensé un poco. El tiempo de acceso HD es en tiempo constante. Dado un HD, tienes un tiempo medio de búsqueda. Entonces, buscar el comienzo de un archivo llevará ese tiempo. – xanatos
La matriz, de manera efectiva, es conocido por una posición de memoria (un puntero). Accediendo a a[3] se puede encontrar en tiempo constante, ya que es solo location_of_a + 3 * sizeof (int).
En C, puede ver esto directamente. Recuerde, 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").
Y como '* (a + 3)' es lo mismo que '* (3 + a)', podemos escribir 'a [3]' también como '3 [a]', un hecho invariablemente útil en IOCCC y similares. :-) – ShreevatsaR
@ShreevatsaR: Sí, pero ... escribir '3 [a]' no tiene muchos usos prácticos, pero usar '* (a + 3)' suele ser útil en escenarios del mundo real. –
Su explicación incluso se mantendría cuando el índice que se usa sea una variable también. Pero como aquí se trata de una constante ('3'), el compilador puede realizar todos los cálculos antes de la ejecución y, en tiempo de ejecución, el programa puede acceder directamente a la memoria. De hecho, no es solo constante, sino realmente pequeña. –
Porque las matrices se almacenan en la memoria de forma secuencial. Entonces, cuando accedes a la matriz [3] le estás diciendo a la computadora: "Obtén la dirección de memoria del comienzo de la matriz, luego sume 3, luego accede a ese punto". Como agregar lleva tiempo constante, ¡también lo hace el acceso a la matriz!
En realidad, agregas 3 multiplicado por el tamaño de los elementos de la matriz. – Matteo
Bueno, sí, pero este es uno de esos temas que requiere un capítulo para explicar con precisión. Estaba omitiendo intencionalmente los detalles para evitar la sobrecarga de información para un principiante. – Phil
"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 requiere básicamente la misma cantidad de tiempo (esto es una simplificación) independientemente del tamaño del contenedor, porque se usa un conjunto fijo de pasos para recuperar el elemento: su ubicación en la memoria (esto también es una simplificación) se calcula y luego se recupera el valor en esa ubicación en la memoria.
Una lista vinculada, por ejemplo, no puede hacer esto, porque cada enlace indica la ubicación de la siguiente. Para encontrar un elemento, debe trabajar con todos los anteriores; en promedio, trabajará en la mitad del contenedor, por lo que obviamente importa el tamaño del contenedor.
una matriz de 10 variables enteras, con índices del 0 al 9, puede almacenarse como 10 palabras en 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 adición. Desde que estas dos operaciones toman tiempo constante. Así podemos decir que el acceso puede realizarse en tiempo constante
Esto es exactamente lo que quería. Es constante, pero ¿qué es matemática detrás de esto? Has explicado muy bien. –
Una matriz es secuencial, lo que significa que la dirección del siguiente elemento en la matriz es al lado del presente. 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 la computadora/accede directamente a la dirección calculada?" Esta es la naturaleza y el principio de la memoria de la computadora (RAM). Si está más interesado en cómo la RAM accede a cualquier dirección en tiempo constante, puede encontrarla en cualquier texto de organización de la computadora o simplemente puede buscarla en Google.
La matriz es una colección de tipos de datos similares. Así que todos los elementos tomarán misma cantidad de memory.Therefore si conoce la dirección base de la matriz y el tipo de datos que contiene se puede conseguir fácilmente elemento de la matriz [i] en tiempo constante utilizando la fórmula indicada 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 i-ésimo elemento en tiempo constante si conoce la dirección base y el tipo de datos que contiene. Visite el enlace this para obtener más información sobre la estructura de datos de matriz.
Si conocemos la ubicación de la memoria a la que se debe acceder, este acceso es en tiempo constante. En el caso de una matriz, la ubicación de la memoria se calcula utilizando el puntero base, el índice del elemento y el tamaño del elemento. Esto implica la operación de multiplicación y adición, que lleva un tiempo constante en ejecutarse. Por lo tanto, el acceso al elemento dentro de la matriz lleva un tiempo constante.
¿por qué esto es downvoted? Por favor, dar una explicación? – pixelearth
no sé por qué ha sido rechazado –
Solo 10 votos favorables. Esto merece atención –