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 ✨.
.
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
Introducción
Arrays y Strings para resolver algoritmos avanzados
Arrays y Strings en detalle
Dos Apuntadores
Patrón de Dos Apuntadores
Verifying Alien Dictionary: análisis del problema
Solución de Verifying Alien Dictionary
Playground: Verifying Alien Dictionary
Programando Verifying Alien Dictionary con JavaScript
Merge Two Sorted Lists: análisis del problema
Solución de Merge Two Sorted Lists
Playground: Merge Two Sorted Lists
Programando Merge Two Sorted Lists con Python
Container With Most Water: análisis del problema
Solución de Container With Most Water
Playground: Container with Most Water
Programando Container With Most Water con Java
Reto: Trapping Rain Water
Ejercicios recomendados de Dos Apuntadores
Ejercicios resueltos de Dos Apuntadores
Ventana Deslizante
Patrón de Ventana Deslizante
Longest Substring Without Repeating Characters: análisis del problema
Solución de Longest Substring Without Repeating Characters
Playground: Longest Substring Without Repeating Characters
Programando Longest Substring Without Repeating Characters con Python
Ejercicios recomendados de Ventana Deslizante
Ejercicios resueltos de Ventana Deslizante
Búsqueda Binaria
Algoritmo de Búsqueda Binaria
Search in Rotated Arrays: análisis del problema
Solución de Search in Rotated Arrays
Playground: Search in Rotated Arrays
Programando Search in Rotated Arrays
Search 2D Array Matrix: análisis del problema
Solución de Search 2D Array Matrix
Playground: Search 2D Array Matrix
Programando Search 2D Array Matrix
Próximos pasos
Toma el Curso Avanzado de Algoritmos: Estructuras de Datos Lineales
Arrays y Strings en detalle
2/35Lectura
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
El texto proporcionado contiene algunas inexactitudes, especialmente en la descripción de la implementación de arrays dinámicos y estáticos, y sus complejidades temporales asociadas a diferentes operaciones. Aquí está una versión corregida del texto:
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.
- Al final:
- 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).
Aportes 10
Preguntas 2
Ordenar por:
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.
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.
¿No puedo borrar ni editar comentarios? jaja
Debía ser "¿Esto que significa? que no pueden ser ..."
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.
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?
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.
¿Quieres ver más aportes, preguntas y respuestas de la comunidad?