Estructuras de datos: fundamentos de algoritmos

Un algoritmo es un procedimiento paso a paso que define un conjunto de instrucciones que se ejecutarán en un orden u otro para producir un resultado deseado. Los algoritmos generalmente se crean independientemente de los lenguajes de programación subyacentes, es decir, con la posibilidad de implementación en varios lenguajes.

En términos de estructuras de datos, las siguientes categorías de algoritmos son importantes:

• Algoritmo para encontrar un elemento en una estructura de datos.
• Un algoritmo para ordenar elementos en un orden específico.
• Algoritmo para insertar un elemento en una estructura de datos.
• Algoritmo para cambiar un elemento presente en la estructura de datos.
• Algoritmo para eliminar un elemento de una estructura de datos.

Características del algoritmo

No todos los procedimientos pueden llamarse algoritmos. El algoritmo debe tener las siguientes características:

• Unambigüedad. El algoritmo debe ser claro e inequívoco. Cada uno de sus pasos, así como los datos de entrada/salida, deben ser claros y dar como resultado un solo valor.
• Datos de entrada. El algoritmo debe tener entradas bien definidas, pero puede que no haya entradas.
• Producción. El algoritmo debe tener salidas bien definidas y ser consistente con la salida deseada.
• Miembro. Los algoritmos deben terminar después de un número finito de pasos.
• Factibilidad. Debe ser factible con los recursos disponibles.
• Independencia. El algoritmo debe tener instrucciones paso a paso independientes de cualquier código de programa.

¿Cómo escribir un algoritmo?

Más bien depende de la tarea y los recursos. No existen estándares bien definidos para escribir algoritmos. Los algoritmos nunca se escriben para admitir este o aquel código de programa.

Como sabe, todos los lenguajes de programación tienen construcciones de código básicas comunes, como bucles ( do , for , while ), control de flujo ( if-else ), etc. Estas construcciones comunes se pueden usar para escribir un algoritmo.

Los algoritmos generalmente se escriben paso a paso, pero no siempre. La escritura de algoritmos es un proceso que se realiza después de que el dominio del problema ha sido claramente definido. Es decir, debe conocer el área del problema para el cual se está desarrollando la solución.

Ejemplo

Intentemos aprender a escribir algoritmos con el ejemplo.

Tarea: desarrollar un algoritmo para sumar dos números y mostrar el resultado:

Los algoritmos les dicen a los programadores cómo escribir el código del programa. El algoritmo también se puede escribir así:

En el desarrollo y análisis de algoritmos, el segundo método suele utilizarse para describir el algoritmo. Esto nos permite simplificar su análisis ignorando todas las definiciones no deseadas. El analista puede observar qué operaciones se están utilizando y cómo avanza el proceso.

Los números de paso son opcionales.

El algoritmo se desarrolla para obtener una solución al problema. Y el problema puede tener varias soluciones:

Por lo tanto, se pueden desarrollar algoritmos con múltiples soluciones para el problema. El siguiente paso es analizar estos algoritmos propuestos e implementar la solución más adecuada.

Análisis de algoritmos

La efectividad del algoritmo se puede analizar en dos etapas diferentes: antes y después de la implementación. Aquí están los pasos:

• El análisis a priori  es el análisis teórico de un algoritmo. El rendimiento de un algoritmo se mide asumiendo que todos los demás factores, como la velocidad del procesador, se mantienen constantes y no afectan la implementación.
• El análisis a posteriori  es un análisis empírico de un algoritmo. El algoritmo seleccionado se implementa utilizando un lenguaje de programación y luego se ejecuta en la computadora de destino. Este análisis recopila estadísticas reales, como el tiempo de ejecución y el espacio requerido.

Estudiemos el análisis a priori de los algoritmos. A la hora de analizar algoritmos se tiene en cuenta el tiempo de ejecución o duración de las distintas operaciones implicadas. El tiempo de ejecución de una operación se puede definir como el número de comandos ejecutados por la computadora en una operación.

Complejidad del algoritmo

Sea X  un algoritmo, n  el tamaño de los datos de entrada y el tiempo y el espacio utilizados en el algoritmo X son los dos factores principales que determinan su eficacia.

• Factor tiempo. El tiempo se mide contando el número de operaciones clave, como las comparaciones en un algoritmo de clasificación.
• factor espacial. El espacio se mide contando la cantidad máxima de memoria requerida por el algoritmo.

La complejidad de un algoritmo, f(n) , determina el tiempo de ejecución y/o el espacio en disco requerido por el algoritmo, donde n  es el tamaño de la entrada.

Complejidad espacial

La complejidad espacial de un algoritmo es la cantidad de memoria requerida por el algoritmo durante su ciclo de vida. Este volumen consta de dos partes:

• La parte fija, es decir, el espacio necesario para almacenar determinados datos y variables, independientemente del tamaño de la tarea. Por ejemplo, variables simples y constantes utilizadas, tamaño del programa, etc.
• La parte mutable, es decir, el espacio que necesitan las variables según el tamaño de la tarea. Por ejemplo, asignación de memoria dinámica, espacio de pila de recursión, etc.

La complejidad espacial S(P) de cualquier algoritmo P se define como S(P) = C + SP(I), donde C es fijo y SP(I) es la parte variable del algoritmo dependiendo de la característica de la instancia I. Aquí hay un ejemplo simple que explica este concepto:

Hay tres variables A, B y C y una constante. Por lo tanto, la complejidad del espacio es S(P) = 1 + 3. El espacio depende de los tipos de datos de las variables dadas y los tipos de constantes y aumentará en consecuencia.

Complejidad del tiempo

La complejidad temporal de un algoritmo es la cantidad de tiempo que lleva completar el algoritmo. Puede definirse como una función numérica T(n), donde T(n) puede medirse por el número de pasos, siempre que cada paso tome un tiempo constante.

Por ejemplo, sumar dos números enteros de n bits toma n pasos. Entonces, el tiempo computacional total es T(n) = c ∗ n, donde c es el tiempo requerido para sumar dos bits. Aquí, T(n) crece linealmente a medida que aumenta el tamaño de la entrada.