Notas Clase: Estructuras de Datos y Análisis de Algorítmos
Introducción a la complejidad de algoritmos
El análisis algorítmico es una técnica utilizada en la ciencia de la computación para evaluar la eficiencia de los algoritmos. En el contexto de las estructuras de datos, el análisis algorítmico se utiliza para evaluar cuánto tiempo y espacio se requieren para realizar operaciones en la estructura de datos.
Una técnica común utilizada en el análisis algorítmico es la notación “Big O”. Esta notación describe la tasa de crecimiento del tiempo o del espacio requerido a medida que el tamaño del problema aumenta. Por ejemplo, un algoritmo con una complejidad de O(n) requerirá aproximadamente n operaciones para un problema de tamaño n. Un algoritmo con una complejidad de O(n^2) requerirá aproximadamente n^2 operaciones para un problema de tamaño n.
La elección adecuada de la estructura de datos y el algoritmo es clave para optimizar tanto el tiempo como el espacio requerido al resolver un problema computacional. Por ejemplo, si se necesita realizar una gran cantidad de búsquedas en una estructura de datos, es importante elegir una estructura de datos que permita búsquedas eficientes, como un árbol de búsqueda binario. Si se necesita realizar muchas inserciones y eliminaciones en la estructura de datos, es importante elegir una estructura de datos que permita inserciones y eliminaciones eficientes, como una lista enlazada.
Es importante tener en cuenta la complejidad de los algoritmos y la eficiencia de las estructuras de datos al diseñar sistemas informáticos y algoritmos, ya que una mala elección puede resultar en una aplicación lenta o incluso inutilizable para problemas grandes.
En la ciencia de la computación, la complejidad de los algoritmos es una medida de la cantidad de recursos necesarios para resolver un problema computacional. Uno de los aspectos clave de la complejidad de los algoritmos es la elección adecuada de las estructuras de datos.
Tipos de datos primitivos en estructuras de datos
Los tipos de datos primitivos son los bloques básicos de construcción de cualquier programa. En estructuras de datos, los tipos de datos primitivos se utilizan para almacenar información de forma eficiente y para realizar operaciones en ella.
Los tipos de datos primitivos más comunes en estructuras de datos son:
Enteros: se utilizan para almacenar números enteros, como 1, 2, 3, etc. Los enteros se utilizan a menudo para realizar operaciones aritméticas, como sumas y restas.
Flotantes: se utilizan para almacenar números decimales, como 1.23, 2.34, etc. Los flotantes se utilizan a menudo para realizar operaciones matemáticas más complejas, como cálculos de porcentajes.
Caracteres: se utilizan para almacenar caracteres individuales, como ‘a’, ‘b’, ‘c’, etc. Los caracteres se utilizan a menudo en la entrada y salida de datos.
Booleanos: se utilizan para almacenar valores verdaderos o falsos. Los booleanos se utilizan a menudo en la toma de decisiones en programas.
Cadenas: se utilizan para almacenar una secuencia de caracteres, como “hola”, “mundo”, etc. Las cadenas se utilizan a menudo para manejar texto.
Por ejemplo, un algoritmo con una complejidad de O(n) requerirá aproximadamente n operaciones para un problema de tamaño n. Un algoritmo con una complejidad de O(n^2) requerirá aproximadamente n^2 operaciones para un problema de tamaño n. Es importante tener en cuenta la complejidad de los algoritmos al diseñar sistemas informáticos y algoritmos, ya que una mala elección puede resultar en una aplicación lenta o incluso inutilizable para problemas grandes.
Notación Big O
La notación “Big O” es una técnica común utilizada en el análisis algorítmico para describir la tasa de crecimiento del tiempo o del espacio requerido a medida que el tamaño del problema aumenta en las estructuras de datos. Por ejemplo, un algoritmo con una complejidad de O(n) requerirá aproximadamente n operaciones para un problema de tamaño n. Un algoritmo con una complejidad de O(n^2) requerirá aproximadamente n^2 operaciones para un problema de tamaño n.
Al elegir una estructura de datos y algoritmo, es importante tener en cuenta la complejidad de los algoritmos y la eficiencia de las estructuras de datos al resolver un problema computacional. Si se necesita realizar una gran cantidad de búsquedas en una estructura de datos, es importante elegir una estructura de datos que permita búsquedas eficientes, como un árbol de búsqueda binario. Si se necesita realizar muchas inserciones y eliminaciones en la estructura de datos, es importante elegir una estructura de datos que permita inserciones y eliminaciones eficientes, como una lista enlazada.
A continuación se presentan algunos ejemplos de complejidad “Big O” en estructuras de datos comunes:
Arreglos: la búsqueda y la inserción en arreglos tienen una complejidad de O(n), donde n es el tamaño del arreglo. La eliminación tiene una complejidad de O(n) en el peor de los casos, ya que se requiere mover los elementos posteriores.
Listas enlazadas: la búsqueda en una lista enlazada tiene una complejidad de O(n), ya que se debe recorrer la lista de principio a fin. La inserción y la eliminación tienen una complejidad de O(1) en el mejor de los casos, ya que se puede agregar o eliminar un elemento en cualquier posición de la lista.
Árboles binarios de búsqueda: la búsqueda, la inserción y la eliminación en un árbol binario de búsqueda tienen una complejidad de O(log n) en el promedio y en el peor de los casos, donde n es el número de elementos en el árbol. Esto se debe a que el árbol está equilibrado y se puede descartar la mitad de los nodos en cada paso.
Montículos: la inserción en un montículo tiene una complejidad de O(log n), donde n es el número de elementos en el montículo. La eliminación tiene una complejidad de O(log n) en el peor de los casos, ya que se debe reorganizar el montículo después de eliminar el elemento superior.
Peor, mejor y promedio
En análisis de algoritmos, los términos caso peor, caso mejor y caso promedio tienen los siguientes significados:
Caso mejor: se refiere a la situación inicial de los datos que genera una ejecución del algoritmo con una menor complejidad computacional.
Caso peor: se refiere a la situación inicial de los datos que genera una ejecución del algoritmo con una complejidad computacional mayor.
Caso promedio: la situación inicial de los datos no sigue ningún patrón preestablecido que aporte ventajas o desventajas. Se puede considerar, por tanto, la situación típica de ejecución del algoritmo.
Considere un algoritmo para encontrar un elemento en una matriz en forma iterativa. El algoritmo se detiene cuando se encuentra el valor. El algoritmo se descompone de la siguiente manera: asignación de 0 a i, siempre que i no haya atravesado la matriz, incrementamos i, si tab [i] = valor, devolvemos verdadero, de lo contrario, al final de la matriz devolvemos falso. Sea C la complejidad del cuerpo del bucle.
En el peor de los casos, el algoritmo recorre toda la tabla, es decir, T (n) = 1 + n * C = O (n). En el mejor de los casos, el elemento está al comienzo de la matriz, por lo que T (n) = 1 + C = O (1). Consideramos que, en promedio, hay una probabilidad de 50% de que el elemento no esté en la matriz y 50% de que esté en el medio de la matriz (esto, por supuesto, es absurdo, pero no haremos todas las posibilidades). En este caso, la complejidad en promedio es T (n) = 0.5 * (1 + n * C) + 0.5 * (1 + n * C / 2) = a * n + b con a y b constantes = O (no ). Observamos que el comportamiento asintótico en promedio es el mismo que en el peor de los casos.