Una array es una estructura de datos lineal. En una array, la operación para obtener un valor toma un tiempo constante, es decir, O(1). Veamos por qué es así.
¿Por qué la complejidad de obtener valor es O (1)?
Como las arrays se asignan de forma contigua en la memoria, obtener un valor a través de un índice de la array es una operación aritmética. Todas las operaciones aritméticas se realizan en tiempo constante, es decir, O(1) .
Explicación:
En una array, tenemos la dirección de memoria de índice 0 (dirección base). Al sumar el producto del número de índice (del valor que se busca) y el tamaño de un elemento (por ejemplo, el tamaño int es de 4 bytes) con la dirección base, podemos obtener la dirección del valor de ese índice. no tenemos que iterar a través de la array. Entonces se hace en O(1).
Dirección del índice i = Dirección base + desplazamiento = Dirección del índice 0 + i × (tamaño de un elemento)
Ejemplo:
Asignación de memoria en array
En la array A[] = {8, 6, 7, 13, 8, 19}
Para obtener el valor en el índice 4 , necesitamos la dirección de memoria donde se almacena el valor de ese índice. La dirección se puede obtener haciendo una operación aritmética, es decir
Dirección del valor en el índice 4 = Dirección del valor del índice 0 + 4 × tamaño de int = 108 + 4 × 4 bytes
Dirección del valor en el índice 4 = 124
A[4] = valor en la dirección 124 = 8
Para más detalles, consulte:
Diseño y Análisis de Algoritmos .