¿Qué es el algoritmo? Introducción a los Algoritmos

¿Qué es un algoritmo? Conceptos básicos del algoritmo

La palabra Algoritmo significa “ Un conjunto de reglas a seguir en los cálculos u otras operaciones de resolución de problemas ” o “ Un procedimiento para resolver un problema matemático en un número finito de pasos que frecuentemente mediante operaciones recursivas ”. 

Por lo tanto, el algoritmo se refiere a una secuencia de pasos finitos para resolver un problema particular.

Los algoritmos pueden ser simples y complejos dependiendo de lo que quieras lograr.

Se puede entender tomando el ejemplo de cocinar una nueva receta. Para cocinar una nueva receta, uno lee las instrucciones y los pasos y los ejecuta uno por uno, en la secuencia dada. El resultado así obtenido es el nuevo plato cocinado a la perfección. Cada vez que usa su teléfono, computadora, computadora portátil o calculadora, está usando algoritmos. De manera similar, los algoritmos ayudan a realizar una tarea en la programación para obtener el resultado esperado.

Los algoritmos diseñados son independientes del idioma, es decir, son simplemente instrucciones que se pueden implementar en cualquier idioma y, sin embargo, el resultado será el mismo, como se esperaba.

¿Cuáles son las características de un algoritmo?

Como uno no seguiría ninguna instrucción escrita para cocinar la receta, sino solo la estándar. Del mismo modo, no todas las instrucciones escritas para la programación son algoritmos. Para que una instrucción sea un algoritmo, debe tener las siguientes características:

• Claro e inequívoco : el algoritmo debe ser claro e inequívoco. Cada uno de sus pasos debe ser claro en todos los aspectos y debe conducir a un solo significado.
• Entradas bien definidas : si un algoritmo dice que tome entradas, deben ser entradas bien definidas. 
• Salidas bien definidas: el algoritmo debe definir claramente qué salida se producirá y también debe estar bien definida. 
• Finitud: el algoritmo debe ser finito, es decir, debe terminar después de un tiempo finito.
• Factible: El algoritmo debe ser simple, genérico y práctico, de manera que pueda ejecutarse con los recursos disponibles. No debe contener alguna tecnología futura ni nada.
• Idioma independiente: el algoritmo diseñado debe ser independiente del idioma, es decir, debe ser simplemente instrucciones que se pueden implementar en cualquier idioma y, sin embargo, el resultado será el mismo, como se esperaba.

Propiedades del algoritmo:

• Debe terminar después de un tiempo finito.
• Debe producir al menos una salida.
• Debería tomar cero o más entradas.
• Debería ser un medio determinista que proporcione la misma salida para el mismo caso de entrada.
• Cada paso en el algoritmo debe ser efectivo, es decir, cada paso debe hacer algún trabajo.

Tipos de Algoritmos:

Hay varios tipos de algoritmos disponibles. Algunos algoritmos importantes son:

1. Algoritmo de fuerza bruta : es el enfoque más simple para un problema. Un algoritmo de fuerza bruta es el primer enfoque que viene a encontrar cuando vemos un problema.

2. Algoritmo recursivo : un algoritmo recursivo se basa en la recursividad . En este caso, un problema se divide en varias subpartes y se llama a la misma función una y otra vez.

3. Algoritmo de retroceso : el algoritmo de retroceso básicamente construye la solución buscando entre todas las soluciones posibles. Usando este algoritmo, seguimos construyendo la solución siguiendo criterios. Cada vez que falla una solución, rastreamos hasta el punto de falla y construimos sobre la siguiente solución y continuamos este proceso hasta que encontramos la solución o todas las soluciones posibles son atendidas.

4. Algoritmo de búsqueda : Los algoritmos de búsqueda son los que se utilizan para buscar elementos o grupos de elementos de una estructura de datos en particular. Pueden ser de diferentes tipos según su enfoque o la estructura de datos en la que se debe encontrar el elemento.

5. Algoritmo de clasificación : clasificar es organizar un grupo de datos de una manera particular según el requisito. Los algoritmos que ayudan a realizar esta función se denominan algoritmos de clasificación. En general, los algoritmos de clasificación se utilizan para clasificar grupos de datos de manera creciente o decreciente.

6. Algoritmo de hashing :

7. Algoritmo divide y vencerás : este algoritmo divide un problema en subproblemas, resuelve un solo subproblema y combina las soluciones para obtener la solución final. Consta de los siguientes tres pasos:

• Dividir
• Resolver
• Combinar

8. Algoritmo Greedy : En este tipo de algoritmo la solución se construye parte por parte. La solución de la siguiente parte se construye en base al beneficio inmediato de la siguiente parte. La solución que brinde el mayor beneficio se elegirá como la solución para la siguiente parte.

9. Algoritmo de programación dinámica : este algoritmo utiliza el concepto de usar la solución ya encontrada para evitar el cálculo repetitivo de la misma parte del problema. Divide el problema en subproblemas superpuestos más pequeños y los resuelve.

10. Algoritmo aleatorio : en el algoritmo aleatorio usamos un número aleatorio para que brinde un beneficio inmediato. El número aleatorio ayuda a decidir el resultado esperado.

Para obtener más información sobre los tipos de algoritmos, consulte el artículo sobre » Tipos de algoritmos «.

Ventajas de los algoritmos:

• Es fácil de entender.
• Un algoritmo es una representación paso a paso de una solución a un problema dado.
• En Algorithm, el problema se divide en partes o pasos más pequeños, por lo que es más fácil para el programador convertirlo en un programa real.

Desventajas de los algoritmos:

• Escribir un algoritmo lleva mucho tiempo, por lo que consume mucho tiempo.
• Comprender la lógica compleja a través de algoritmos puede ser muy difícil.
• Las declaraciones de ramificación y bucle son difíciles de mostrar en Algorithms (imp) .

¿Cómo diseñar un algoritmo?

Para escribir un algoritmo, se necesitan las siguientes cosas como requisito previo: 
 

1. El problema que debe resolver este algoritmo es una clara definición del problema.
2. Las restricciones del problema deben ser consideradas mientras se resuelve el problema.
3. La entrada a tomar para resolver el problema.
4. La salida que se espera cuando se resuelve el problema.
5. La solución a este problema, está dentro de las restricciones dadas.

Luego, el algoritmo se escribe con la ayuda de los parámetros anteriores de modo que resuelva el problema.
Ejemplo: Considere el ejemplo para sumar tres números e imprimir la suma.
 

• Paso 1: Cumplimiento de los requisitos previos 
  Como se discutió anteriormente, para escribir un algoritmo, se deben cumplir sus requisitos previos. 
  1. El problema que debe resolver este algoritmo : sume 3 números e imprima su suma.
  2. Las restricciones del problema que deben considerarse al resolver el problema : Los números deben contener solo dígitos y ningún otro carácter.
  3. La entrada a tomar para resolver el problema: Los tres números a sumar.
  4. La salida que se espera cuando se resuelve el problema: La suma de los tres números tomados como entrada, es decir, un solo valor entero.
  5. La solución a este problema, en las restricciones dadas: La solución consiste en sumar los 3 números. Se puede hacer con la ayuda del operador ‘+’, o bit a bit, o cualquier otro método.
• Paso 2: Diseñando el algoritmo
  Ahora diseñemos el algoritmo con la ayuda de los requisitos previos anteriores:
  Algoritmo para sumar 3 números e imprimir su suma: 
  1. COMIENZO
  2. Declare 3 variables enteras num1, num2 y num3.
  3. Tome los tres números, para sumar, como entradas en las variables num1, num2 y num3 respectivamente.
  4. Declare una suma variable entera para almacenar la suma resultante de los 3 números.
  5. Suma los 3 números y almacena el resultado en la variable suma.
  6. Imprimir el valor de la variable suma
  7. FINAL
• Paso 3: Probar el algoritmo implementándolo.
  Para probar el algoritmo, implementémoslo en lenguaje C.

Programa:

// C++ program to add three numbers
// with the help of above designed
// algorithm
#include <bits/stdc++.h>
using namespace std;
  
int main()
{
     
    // Variables to take the input of
    // the 3 numbers
    int num1, num2, num3;
  
    // Variable to store the resultant sum
    int sum;
  
    // Take the 3 numbers as input
    cout << "Enter the 1st number: ";
    cin >> num1;
    cout << " " << num1 << endl;
  
    cout << "Enter the 2nd number: ";
    cin >> num2;
    cout << " " << num2 << endl;
  
    cout << "Enter the 3rd number: ";
    cin >> num3;
    cout << " " << num3;
  
    // Calculate the sum using + operator
    // and store it in variable sum
    sum = num1 + num2 + num3;
  
    // Print the sum
    cout << "\nSum of the 3 numbers is: "
         << sum;
  
    return 0;
}
 
// This code is contributed by shivanisinghss2110

// C program to add three numbers
// with the help of above designed algorithm
 
#include <stdio.h>
 
int main()
{
 
    // Variables to take the input of the 3 numbers
    int num1, num2, num3;
 
    // Variable to store the resultant sum
    int sum;
 
    // Take the 3 numbers as input
    printf("Enter the 1st number: ");
    scanf("%d", &num1);
    printf("%d\n", num1);
 
    printf("Enter the 2nd number: ");
    scanf("%d", &num2);
    printf("%d\n", num2);
 
    printf("Enter the 3rd number: ");
    scanf("%d", &num3);
    printf("%d\n", num3);
 
    // Calculate the sum using + operator
    // and store it in variable sum
    sum = num1 + num2 + num3;
 
    // Print the sum
    printf("\nSum of the 3 numbers is: %d", sum);
 
    return 0;
}

// Java program to add the three numbers
// with the help of above designed
// algorithm
import java.util.*;
 
class GFG {
    public static void main(String[] args)
    {
       
        // Variable to store the resultant sum
        int sum = 0;
       
        // Declare the object and initialize with
        // predefined standard input object
        Scanner sc
            = new Scanner(System.in); // Scanner definition
         
      // Variables to take the input of
        // the 3 numbers
        System.out.println("Enter the 1st number: ");
        int num1 = sc.nextInt();
       
      // input is an Integer
        // read by nextInt() function
        System.out.println(" " + num1);
        System.out.println("Enter the 2nd number: ");
        int num2 = sc.nextInt();
        System.out.println(" " + num2);
        System.out.println("Enter the 3rd number: ");
        int num3 = sc.nextInt();
        System.out.println(" " + num3);
       
        // Calculate the sum using + operator
        // and store it in variable sum
        sum = num1 + num2 + num3;
        System.out.println("Sum of the 3 numbers is = "
                           + sum);
    }
}
 
/*This code is contributed by Rishab Dugar*/

# Python3 program to add three numbers
# with the help of above designed
# algorithm
 
 
if __name__ == "__main__":
 
    # Variables to take the input of
    # the 3 numbers
    num1 = num2 = num3 = 0
 
    # Variable to store the resultant sum
    sum = 0
 
    # Take the 3 numbers as input
    num1 = int(input("Enter the 1st number: "))
 
    num2 = int(input("Enter the 2nd number: "))
 
    num3 = int(input("Enter the 3rd number: "))
 
    # Calculate the sum using + operator
    # and store it in variable sum
    sum = num1 + num2 + num3
 
    # Print the sum
    print("\nSum of the 3 numbers is:", sum)

Enter the 1st number: 0
Enter the 2nd number: 0
Enter the 3rd number: -1577141152

Sum of the 3 numbers is: -1577141152

Un problema, muchas soluciones: La solución a un algoritmo puede ser o no ser más de una. Significa que al implementar el algoritmo, puede haber más de un método para implementarlo. Por ejemplo, en el problema anterior para sumar 3 números, la suma se puede calcular de muchas maneras como:

• + operador
• Operadores bit a bit
• . . etc.

¿Cómo analizar un Algoritmo? 

Para que un algoritmo estándar sea bueno, debe ser eficiente. Por lo tanto, la eficiencia de un algoritmo debe verificarse y mantenerse. Puede ser en dos etapas:

1. Análisis a priori: “Priori” significa “antes”. Por lo tanto, el análisis a priori significa verificar el algoritmo antes de su implementación. En este, el algoritmo se comprueba cuando está escrito en forma de pasos teóricos. Esta eficiencia de un algoritmo se mide asumiendo que todos los demás factores, por ejemplo, la velocidad del procesador, son constantes y no tienen efecto en la implementación. Esto lo hace generalmente el diseñador de algoritmos. Este análisis es independiente del tipo de hardware y lenguaje del compilador. Da las respuestas aproximadas para la complejidad del programa.
2. Análisis Posterior: “Posterior” significa “después”. Por lo tanto, el análisis posterior significa verificar el algoritmo después de su implementación. En este se comprueba el algoritmo implementándolo en cualquier lenguaje de programación y ejecutándolo. Este análisis ayuda a obtener el informe de análisis real y real sobre la corrección, el espacio requerido, el tiempo consumido, etc. Es decir, depende del idioma del compilador y del tipo de hardware utilizado.

¿Qué es la complejidad del algoritmo y cómo encontrarla?

Un algoritmo se define como complejo en función de la cantidad de espacio y tiempo que consume. Por lo tanto, la Complejidad de un algoritmo se refiere a la medida del Tiempo que necesitará para ejecutarse y obtener el resultado esperado, y el Espacio que necesitará para almacenar todos los datos (entrada, datos temporales y salida). Por lo tanto, estos dos factores definen la eficiencia de un algoritmo. 
Los dos factores de la complejidad del algoritmo son:

• Factor de tiempo : el tiempo se mide contando el número de operaciones clave, como las comparaciones en el algoritmo de clasificación.
• Factor de espacio : el espacio se mide contando el espacio de memoria máximo requerido por el algoritmo.

Por lo tanto, la complejidad de un algoritmo se puede dividir en dos tipos :

1. Complejidad espacial : la complejidad espacial de un algoritmo se refiere a la cantidad de memoria utilizada por el algoritmo para almacenar las variables y obtener el resultado. Esto puede ser para entradas, operaciones temporales o salidas. 

¿Cómo calcular la Complejidad Espacial?
La complejidad espacial de un algoritmo se calcula determinando los siguientes 2 componentes: 
 

• Parte Fija: Esto se refiere al espacio que definitivamente requiere el algoritmo. Por ejemplo, variables de entrada, variables de salida, tamaño del programa, etc.
• Parte variable: se refiere al espacio que puede ser diferente en función de la implementación del algoritmo. Por ejemplo, variables temporales, asignación de memoria dinámica, espacio de pila de recursión, etc.
  Por lo tanto, 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.

Ejemplo: considere el siguiente algoritmo para la búsqueda lineal

Paso 1: COMENZAR
Paso 2: Obtener la array en arr y el número a buscar en x
Paso 3: Comenzar desde el elemento más a la izquierda de arr[] y uno por uno comparar x con cada elemento de arr[]
Paso 4: Si x coincide con un elemento, Print True.
Paso 5: si x no coincide con ninguno de los elementos, imprima Falso.
Paso 6: FIN
Aquí, hay 2 variables arr[] yx, donde arr[] es la parte variable yx es la parte fija. Por lo tanto S(P) = 1+1. Ahora, el espacio depende de los tipos de datos de variables dadas y tipos constantes y se multiplicará en consecuencia.

2. Complejidad del tiempo : la complejidad del tiempo de un algoritmo se refiere a la cantidad de tiempo que requiere el algoritmo para ejecutarse y obtener el resultado. Esto puede ser para operaciones normales, sentencias if-else condicionales, sentencias de bucle, etc.

¿Cómo calcular la Complejidad del Tiempo?
La complejidad temporal de un algoritmo también se calcula determinando los siguientes 2 componentes: 

• Parte de tiempo constante: En esta parte entra toda instrucción que se ejecuta una sola vez. Por ejemplo, entrada, salida, si no, interruptor, etc.
• Parte de tiempo variable: cualquier instrucción que se ejecuta más de una vez, digamos n veces, entra en esta parte. Por ejemplo, bucles, recursividad, etc.
  Por lo tanto, la complejidad temporal  de cualquier algoritmo P es T(P) = C+ TP(I) , donde C es la parte de tiempo constante y TP(I) es la parte variable del algoritmo, que depende de la característica de la instancia I.

Ejemplo: en el algoritmo de búsqueda lineal anterior, la complejidad del tiempo se calcula de la siguiente manera:

Paso 1: –Tiempo constante Paso 2:
–Tiempo
constante Paso 3: –Tiempo variable (Hasta la longitud de la array, digamos n, o el índice del elemento encontrado)
Paso 4: –Tiempo constante Paso 5:
–Paso de tiempo constante
6: –Tiempo constante
Por lo tanto, T(P) = 5 + n, que se puede decir como T(n).