Arrays y Strings: Funcionamiento y Complejidades Temporales

Curso de Algoritmos Avanzados: Patrones de Arrays y Strings

Contenido del curso

Introducción

Dos Apuntadores

Ventana Deslizante

Búsqueda Binaria

Próximos pasos

35
Estructuras de Datos Lineales: Conceptos y Aplicaciones
00:36 min

Tomar examen

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