Algoritmo es un paso a paso del procedimiento, que define un conjunto de instrucciones para ser ejecutadas en un orden determinado para obtener la salida deseada. 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, a continuación se presentan algunas categorías importantes de Algoritmos −
-
search − algoritmo para buscar un elemento en una estructura de datos.
-
Sort − Algoritmo para ordenar los elementos en un orden determinado.
-
Insert-algoritmo para insertar elemento 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 ser llamados algoritmos., Un algoritmo debe tener las siguientes características –
-
inequívoco-el algoritmo debe ser claro e inequívoco. Cada uno de sus pasos (o fases), y sus entradas/salidas deben ser claras y deben conducir a un solo significado.
-
entrada-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.
-
finitud-los Algoritmos deben terminar después de un número finito de pasos.,
-
Factibilidad-debe ser factible con los recursos disponibles.
-
independiente-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 hay estándares bien definidos para escribir algoritmos. Más bien, depende de los problemas y los recursos. Los algoritmos nunca se escriben para soportar 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 se pueden usar para escribir un algoritmo.
escribimos algoritmos paso a paso, pero no siempre es el caso. 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.
problema-diseñar un algoritmo para añadir dos números y mostrar el resultado.
Step 1 − STARTStep 2 − declare three integers a, b & cStep 3 − define values of a & bStep 4 − add values of a & bStep 5 − store output of step 4 to cStep 6 − print cStep 7 − STOP
Los algoritmos indican a los programadores cómo codificar el programa., Alternativamente, el algoritmo se puede escribir como –
Step 1 − START ADDStep 2 − get values of a & bStep 3 − c ← a + bStep 4 − display cStep 5 − STOP
en el diseño y análisis de Algoritmos, generalmente el segundo método se utiliza para describir un algoritmo. Hace que sea fácil para el analista analizar el algoritmo ignorando todas las definiciones no deseadas. Puede observar qué operaciones se están utilizando y cómo fluye el proceso.
escribir números de pasos es opcional.
diseñamos un algoritmo para obtener una solución de un problema dado. Un problema se puede resolver de más de una manera.,
por lo 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 mejor solución adecuada.
análisis de Algoritmos
la eficiencia de un algoritmo puede analizarse en dos etapas diferentes, antes y después de la implementación. Son los siguientes −
-
a Priori Análisis − 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.
-
Un Análisis Posterior − Este es un análisis empírico de un algoritmo. El algoritmo seleccionado se implementa utilizando lenguaje de programación. Esto se ejecuta en el equipo 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 del equipo ejecutadas por operación.
complejidad del algoritmo
supongamos que 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.
-
factor de tiempo − el tiempo se mide contando el número de operaciones clave, como las comparaciones en el algoritmo de Ordenación.,
-
factor de espacio-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.
Space Complexity
Space complexity of an algorithm represents the amount of memory space required by the algorithm in its life cycle., El espacio requerido por un algoritmo es igual a la suma de los siguientes dos componentes −
-
una parte fija que es un espacio requerido para almacenar ciertos datos y variables, que son independientes del tamaño del problema. Por ejemplo, variables simples y constantes usadas, tamaño del programa, etc.
-
Una parte variable es un espacio requerido por las variables, cuyo tamaño depende del tamaño del problema. Por ejemplo, asignación de memoria dinámica, espacio de pila recursiva, etc.,
Space complexity 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. a continuación se muestra un ejemplo simple que intenta explicar el concepto −
Algorithm: SUM(A, B)Step 1 - STARTStep 2 - C ← A + B + 10Step 3 - Stop
Aquí tenemos tres variables A, B y C y una constante. Por lo tanto S(P) = 1 + 3. Ahora, el espacio depende de los tipos de datos de variables dadas y tipos constantes y se multiplicará en consecuencia.,
complejidad de tiempo
la complejidad de tiempo de un algoritmo representa la cantidad de tiempo requerido por 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 tiempo constante.
por ejemplo, la adición de dos enteros de n bits toma n pasos. En consecuencia, el tiempo computacional total es T ( n) = c ∗ n, donde c es el tiempo necesario para la adición de dos bits. Aquí, observamos que T (n) crece linealmente a medida que aumenta el tamaño de entrada.,