Estructuras de datos: conceptos básicos de algoritmos

El algoritmo es un procedimiento paso a paso, que define un conjunto de instrucciones que se ejecutarán en un orden determinado para obtener el resultado deseado. Los algoritmos generalmente se crean independientemente de los lenguajes subyacentes, es decir, un algoritmo se puede implementar en más de un lenguaje de programación.

Desde el punto de vista de la estructura de datos, las siguientes son algunas categorías importantes de algoritmos:

• Search - Algoritmo para buscar un elemento en una estructura de datos.

• Sort - Algoritmo para clasificar elementos en un orden determinado.

• Insert - Algoritmo para insertar elementos en una estructura de datos.

• Update - Algoritmo para actualizar un elemento existente en una estructura de datos.

• Delete - Algoritmo para eliminar un elemento existente de una estructura de datos.

Características de un algoritmo

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

• Unambiguous- El algoritmo debe ser claro e inequívoco. Cada uno de sus pasos (o fases), y sus entradas / salidas deben ser claros y deben conducir a un solo significado.

• Input - Un algoritmo debe tener 0 o más entradas bien definidas.

• Output - Un algoritmo debe tener 1 o más salidas bien definidas y debe coincidir con la salida deseada.

• Finiteness - Los algoritmos deben terminar después de un número finito de pasos.

• Feasibility - Debe ser factible con los recursos disponibles.

• Independent - Un algoritmo debe tener instrucciones paso a paso, que deben ser independientes de cualquier código de programación.

¿Cómo escribir un algoritmo?

No existen estándares bien definidos para escribir algoritmos. Más bien, depende del problema y de los recursos. Los algoritmos nunca se escriben para admitir un código de programación en particular.

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

Escribimos algoritmos paso a paso, pero no siempre es así. La escritura de algoritmos es un proceso y se ejecuta después de que el dominio del problema esté bien definido. Es decir, debemos conocer el dominio del problema, para el cual estamos diseñando una solución.

Ejemplo

Intentemos aprender a escribir algoritmos usando un ejemplo.

Problem - Diseñar un algoritmo para sumar dos números y mostrar el resultado.

Step 1 − START
Step 2 − declare three integers a, b & c
Step 3 − define values of a & b
Step 4 − add values of a & b
Step 5 − store output of step 4 to c
Step 6 − print c
Step 7 − STOP

Los algoritmos les dicen a los programadores cómo codificar el programa. Alternativamente, el algoritmo se puede escribir como:

Step 1 − START ADD
Step 2 − get values of a & b
Step 3 − c ← a + b
Step 4 − display c
Step 5 − STOP

En el diseño y análisis de algoritmos, normalmente se utiliza el segundo método para describir un algoritmo. Facilita al analista analizar el algoritmo ignorando todas las definiciones no deseadas. Puede observar qué operaciones se están utilizando y cómo fluye el proceso.

Escritura step numbers, es opcional.

Diseñamos un algoritmo para obtener la solución de un problema determinado. Un problema se puede resolver de más de una forma.

Por tanto, se pueden derivar muchos algoritmos de solución para un problema dado. El siguiente paso es analizar los algoritmos de solución propuestos e implementar la solución más adecuada.

Análisis de algoritmos

La eficiencia de un algoritmo se puede analizar en dos etapas diferentes, antes de la implementación y después de la implementación. Son los siguientes:

• A Priori Analysis- Este es un análisis teórico de un algoritmo. La eficiencia de un algoritmo se mide asumiendo que todos los demás factores, por ejemplo, la velocidad del procesador, son constantes y no tienen ningún efecto en la implementación.

• A Posterior Analysis- Este es un análisis empírico de un algoritmo. El algoritmo seleccionado se implementa mediante lenguaje de programación. Esto luego se ejecuta en la computadora de destino. En este análisis, se recopilan estadísticas reales como el tiempo de ejecución y el espacio requerido.

Aprenderemos sobre el análisis de algoritmos a priori . El análisis de algoritmos se ocupa de la ejecución o el tiempo de ejecución de varias operaciones involucradas. El tiempo de ejecución de una operación se puede definir como el número de instrucciones de computadora ejecutadas por operación.

Complejidad del algoritmo

Suponer X es un algoritmo y n es el tamaño de los datos de entrada, el tiempo y el espacio utilizados por el algoritmo X son los dos factores principales que deciden la eficiencia de X.

• Time Factor - El tiempo se mide contando el número de operaciones clave, como comparaciones, en el algoritmo de clasificación.

• Space Factor - El espacio se mide contando el espacio de memoria máximo requerido por el algoritmo.

La complejidad de un algoritmo f(n) da el tiempo de ejecución y / o el espacio de almacenamiento requerido por el algoritmo en términos de n como el tamaño de los datos de entrada.

Complejidad espacial

La complejidad espacial de un algoritmo representa la cantidad de espacio de memoria que requiere el algoritmo en su ciclo de vida. El espacio requerido por un algoritmo es igual a la suma de los siguientes dos componentes:

• Una parte fija que es un espacio necesario para almacenar ciertos datos y variables, que son independientes del tamaño del problema. Por ejemplo, variables simples y constantes utilizadas, tamaño del programa, etc.

• Una parte variable es un espacio requerido por variables, cuyo tamaño depende del tamaño del problema. Por ejemplo, asignación de memoria dinámica, espacio de pila de recursividad, etc.

La complejidad espacial S (P) de cualquier algoritmo P es S (P) = C + SP (I), donde C es la parte fija y S (I) es la parte variable del algoritmo, que depende de la característica de instancia I. es un ejemplo simple que intenta explicar el concepto -

Algorithm: SUM(A, B)
Step 1 -  START
Step 2 -  C ← A + B + 10
Step 3 -  Stop

Aquí tenemos tres variables A, B y C y una constante. Por tanto, S (P) = 1 + 3. Ahora, el espacio depende de los tipos de datos de las variables dadas y de los tipos de constantes y se multiplicará en consecuencia.

Complejidad del tiempo

La complejidad temporal de un algoritmo representa la cantidad de tiempo que necesita el algoritmo para ejecutarse hasta su finalización. Los requisitos de tiempo se pueden definir como una función numérica T (n), donde T (n) se puede medir como el número de pasos, siempre que cada paso consuma un tiempo constante.

Por ejemplo, la suma de dos enteros de n bits toma npasos. En consecuencia, el tiempo computacional total es T (n) = c ∗ n, donde c es el tiempo necesario para la suma de dos bits. Aquí, observamos que T (n) crece linealmente a medida que aumenta el tamaño de entrada.