Te damos la bienvenida a esta clase de arrays y strings en detalle. 💚
En esta clase veremos cómo funcionan los arrays en diferentes lenguajes de programación, y también en qué se relacionan con los strings. ¡Empecemos! 👨🚀🚀
Arrays
Es una colección lineal de valores de datos a los que se puede acceder utilizando índices numerados que inician en 0.
Es importante conocer cómo están implementadas las estructuras de datos en el lenguaje de programación que estés utilizando, pues esto podría influir en la complejidad temporal de las operaciones con la estructura. Por ejemplo, en JavaScript y Python, los arrays están implementados como arrays dinámicos.
Un array dinámico es una implementación de una matriz que asigna preventivamente más memoria de la necesaria para almacenar los valores de la matriz, permitiendo así crecer dinámicamente. La adición de valores al array no es siempre una operación de tiempo constante; es de tiempo constante (amortizado) en promedio, pero puede requerir una operación más costosa de tiempo lineal (O(n)) cuando se necesita expandir y copiar la matriz a una nueva ubicación de memoria con más espacio.
Por otro lado, existen los arrays estáticos, en los cuales se asigna una cantidad fija de memoria para almacenar los valores desde el inicio. En la mayoría de los contextos de programación, añadir valores a un array estático tal como se describe (copiando toda la matriz y asignando nueva memoria para ella cada vez que se añade un valor) no es una práctica común debido a su ineficiencia; esta descripción se aplica más correctamente a las operaciones de expansión de un array dinámico. Los arrays estáticos no permiten añadir más elementos de los que su tamaño fijo permite, por lo que la operación descrita no aplica.
A continuación, se describen las operaciones estándar de un array y sus correspondientes complejidades temporales corregidas:
Acceso a un valor en un índice determinado: O(1)
Actualización de un valor en un índice dado: O(1)
Inserción de un valor:
Al final: O(1) amortizado para un array dinámico; no aplicable a arrays estáticos en el sentido tradicional, ya que su tamaño es fijo.
En cualquier otra posición: O(n) para un array dinámico, ya que puede requerir desplazar elementos.
Eliminación de un valor al principio: O(n), ya que requiere desplazar todos los demás valores.
Eliminación de un valor en el medio: O(n), por la misma razón.
Eliminación de un valor al final: O(1) para un array dinámico.
Copiar el array: O(n)
Strings
Los Strings no son una estructura de datos como tal sino un array cuyos valores son todos caracteres, estos caracteres se almacenan en la memoria como listas de números enteros, en cada carácter de una cadena se asigna a un número entero mediante un estándar de codificación de caracteres como ASCII.
Las cadenas se comportan de forma muy parecida a las matrices normales, con la principal diferencia de que, en la mayoría de los lenguajes de programación (C++ es una notable excepción), las cadenas son inmutables. Esto que significa que no pueden ser editadas después de su creación. Esto también significa que operaciones simples como añadir un carácter a una cadena son más caras de lo que parece. Por ejemplo:
La operación anterior tiene una complejidad de tiempo de O(n2), donde n es la longitud de la cadena. Porque cada adición de un carácter a nuevaString crea una cadena completamente nueva y es en sí misma una operación O(n). Por lo tanto, se realizan n operaciones O(n), entonces la complejidad es O(n*n).
Arrays y Strings: Funcionamiento y Complejidades Temporales
Si el elemento que necesita ser borrado está presente en arr[0], necesitamos desplazar todos los elementos desde el índice 1 a N - 1 (donde N es el tamaño del arreglo), movemos todos los elementos una posición a la izquierda. Sin embargo, hay otras formas de implementar la lista en la que esta complejidad puede ser diferente.
Una forma de "remover" el último valor en complejidad temporal de O(1) es cambiar el N a ser N-1, entonces cuando iteres o accedas a los valores si antes tenias N definido como 100 y lo cambias a 99, ya no accederás al ultimo espacio en memoria ya que el indice nunca llegará hasta allí... dependiendo del lenguaje que utilices y como este maneje la memoria deberas hacerte cargo o no de liberar ese espacio en memoria que queda al final
Y en python los "array" si reservan de forma preventiva el doble de la cantidad memoria necesaria para almacenar los valores que se le van ingresando. Pero en C es diferente.
Un array dinámico es una estructura que permite cambiar su tamaño en tiempo de ejecución. La estrategia que se use si varía dependiendo del lenguaje.
Me gustan las preguntas o comentarios que dejaste son bastante profundos en cuanto a memoria.
En C un array no existe como tal. en su lugar tienes memoria reservada y punteros.
Con C si deseas tener array’s dinámicos tendrías que implementarlos con el uso de la función malloc o realloc y hacerlos crecer al doble pero tu debes implementarlo.
En Python debes usarlo pero no puedes implementarlo de cero.
Python al estar escrito en C por debajo usa el mismo array los malloc y reallocs y un montón de cosas mas como clases objetos y métodos que quizás ni uses en tus algoritmos.
Es esto precisamente lo que hace GENIAL C, ps Tu tienes el *Control sobre La Memoria y el OS General, y eso da muchos superPoderes que conllevan una gran responsabilidadad al programar ps tendras que hacerte cargo del Garbage Collector y de liberar la memoria que ya no uses para evitar Memory Leaks que fugan la memoria y nunca la devuelven arrastran tu RAM al borde del Crash. C es un Gran Lenguaje que no abstrae todo lo que hace Python ahora super AltoNivel, El mejor Lenguaje de Programacion es aquel se se te adapte mejor a tus necesidades de Proyecto.s .
Yo tengo una duda tambien respecto a lo indica el texto, ya que este indica que en arrays estaticos, cuando se añade un nuevo elemento de debe copiar toda la matriz y asignar un nuevo espacio en memoria dado el nuevo elemento y especifica que este tiene una complejidad O(n) pero cuando dice insercion de un valor mas abajo concluye como O(1) para estatica entonces que situacion hace que cambie el calculo?
Los strings y arrays son pan de cada dia, bien sea que lo recibamos de una api o que la respuesta de la api se convierta a estas estructuras para su posterior manejo
No puedo decir que quedo todo muy claro hasta que no lo implemente 😅. Lo que si me confirma es que así se use un break para el mejor de los casos, el Big O es basado en el peor de los casos.
Tengo una duda.
Para mi, la complejidad temporal para acceder a un valor en un indice determinado en Java si sería de O(1) pero en Python los vectores al ser listas tienen un puntero al siguiente elemento de la lista y acceder a un elemento por su índice implicaría una búsqueda secuencia de O(n)
¿Estoy equivocada?
Time Complexiy in python
Ambos tiene complejidad O(1) para acceder a un valor tanto el ArrayList de java como el list de python.
Ambos son ADT son abstract data types que por dentro tiene un array y solo te dan los métodos ya hechos para usar esa estructura.
Si tienen un array y lo implementan por que le ponen list y nos confunden así. jaja para mantener concentrados los programadores supongo o por que son de una sola dimensión el arreglo.
En resumen en python list no significa lista enlazada si no arreglo dinamico.
Bueno, tampoco es del todo cierto. En muchos lenguajes de programación si se usa el "zero-based indexing" donde los índices numerados inician en cero. Pero también hay lenguajes 'one-based indexing' como R donde el primer elemento de un vector tiene el índice 1.
Muy interesante.
Aunque el lenguaje de programación defina la sintaxis que usa el programador el manejo de memoria lo da el sistema operativo como el kernel de Linux, o Windows NT o XNU para mac es quien pagina y asigna la memoria ya que los sistemas operativos SO están escritos en C/C++ aunque uses R y veas que empieza desde 1 la memoria funciona igual desde 0.
