Arrays y Strings: Funcionamiento y Complejidades Temporales

Clase 2 de 35 • Curso de Algoritmos Avanzados: Patrones de Arrays y Strings

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

Luis Fernando Rodriguez Boett

student•

Me gusta mucho que hayan colocado el analisis asintotico (complejidad algoritmica) en la explicación. Son detalles que se deben tomar en cuenta al momento de programar y que mejoran la eficiencia del algoritmo :sparkles:. . Hice un post explicando acerca de ello. Pueden ir a leerlo en este link Si quieren saber más sobre complejidad algoritmica, pueden ir a este curso

Gabriel Morales

student•

¿Por qué al eliminar un valor al principio de un array tiene una complejidad de O(n) y al final O(1)? ¿No debería ser al revés?

Camila Londoño

teacher•

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.

Camila Londoño

teacher•

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

Andrea Bertieri

student•

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.

William Rodriguez

student•

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.

Bryan Castano

student•

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 .

Edwin Garcés Saucedo

student•

Hay un pedazo de texto después del subtítulo “Arrays” que parece provenir de un LLM, genera un poco de confusión porque te distrae del contenido principal. Ojalá puedan removerlo.

Ricardo Betancourt

student•

Porque O(n) cuando se trata de una matriz estática ???

Juan Castro

teacher•

Estaba al revés. Ya quedó de la forma correcta. Gracias por el aviso.

Manuel Alejandro Perdomo

student•

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?

Luis Bastidas

student•

Creo que hay un error de lógica en las afirmaciones sobre las inserciones en arreglos dinámicos y estáticos:

En el texto se afirma que la inserción en los arreglos dinámicos es una operación O(1), sin embargo, al enumerar las características de cada uno, más abajo, se indica que es O(n).

Lo mismo pasa con los arreglos estáticos.

José Ramón García

student•

Una forma de hacer el código más eficiente sería:

Pasar el string nuevoString a una lista.

Pues los strings son arrays inmutables y cada vez que hacemos

nuevoString += caracter, estamos copiando todo a un nuevo string, lo que nos da un costo de O(n).

Pero con una lista que es un array dinámico, añadir un valor al final es de costo O(1). nuevoString.append(caracter)

Así el resultado final sería 0(n) y no 0(n²).

Carlos Castro

student•

¿No puedo borrar ni editar comentarios? jaja

Carlos Castro

student•

Debía ser "¿Esto que significa? que no pueden ser ..."

Alberto Gurrion

student•

Es mejor explicar todos los detalles de esto en un video en lugar de solo escribirlo ya que es dificil expresar los detalles en algo así de resumido.

Reinaldo Mendoza

student•

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

Nicolas Alpargatero

student•

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.

Andrea Bertieri

student•

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?

William Rodriguez

student•

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.

Andrea Bertieri

student•

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.

William Rodriguez

student•

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.

Arrays y Strings: Funcionamiento y Complejidades Temporales

Introducción

Patrones de Arreglos y Strings: Ventana Deslizante y Dos Apuntadores

Arrays y Strings: Funcionamiento y Complejidades Temporales

Dos Apuntadores

Patrón de Dos Apuntadores en Algoritmos de Lista

Verificación de Orden en Diccionario Alienígena

Ordenamiento de Palabras en Idiomas Alienígenas

Playground: Verifying Alien Dictionary

Ordenación de Palabras en Diccionario Alienígena

Combinar Listas Ordenadas en un Array Ascendente

Ordenamiento de Listas con Complejidad Óptima y Espacio Constante

Playground: Merge Two Sorted Lists

Intercalación de Listas Ordenadas en Python

Resolver el problema "Container with Most Water" en Python

Cálculo Óptimo de Área en Listas de Alturas

Playground: Container with Most Water

Implementación de solución de cálculo de área máxima en Java

Implementación de Trapping Rainwater en Complejidad Lineal

Retos de Algoritmos con Apuntadores en Python

Patrones de Dos Apuntadores: Soluciones a Problemas Comunes en Python

Ventana Deslizante

Patrón Ventana Deslizante para Análisis de Datos Secuenciales

Subcadena más larga sin caracteres repetidos: patrón ventana deslizante

Algoritmo de Ventana Deslizante para Subcadenas Únicas

Playground: Longest Substring Without Repeating Characters

Algoritmo Python para Substring más Largo Sin Repeticiones

Retos de Algoritmos: Dos Apuntadores y Subcadenas

Máximos 1s Consecutivos y Subcadenas sin Repeticiones

Búsqueda Binaria

Algoritmo de búsqueda binaria en listas ordenadas

Búsqueda en Arrays Rotados: Encontrar Entero en Lista Ordenada

Búsqueda Binaria en Arreglos Rotados

Playground: Search in Rotated Arrays

Búsqueda en Arrays Rotados con C++

Búsqueda eficiente en matriz ordenada MxN

Búsqueda Binaria en Matrices 2D Ordenadas

Playground: Search 2D Array Matrix

Búsqueda Binaria en Matrices con Python

Próximos pasos

Estructuras de Datos Lineales: Conceptos y Aplicaciones