Header Ads Widget

Ticker

6/recent/ticker-posts

¿Cuáles son algunos algoritmos de programación comunes?

 


Para comprender mejor el concepto de algoritmos en la programación de computadoras, imaginemos que tenemos un grupo de varias formas. Puede tener algunas formas circulares, formas ovaladas, cuadrados, rectángulos, triángulos, etc. Su objetivo es agrupar estas diversas formas en varios conjuntos diferentes. Para organizar estas formas con un programa de computadora, tal vez podría configurar un bucle que itera sobre todas las formas y determina qué forma tiene en cada iteración. Cuando se determina su forma, se asigna a un grupo específico. Una vez que se completen todas las iteraciones, tendrá una cierta cantidad de grupos, cada uno con formas similares. La lista completa de pasos necesarios para completar este problema es lo que se conoce como algoritmo . En este tutorial, aprenderemos un poco sobre algoritmos en Python.


Características del algoritmo

Los algoritmos tienen varios rasgos que podemos usar para describirlos. Por ejemplo, los algoritmos tienen complejidad temporal y espacial.

Complejidad del tiempo

La complejidad del tiempo describe qué tan eficiente es un algoritmo en relación con el tamaño de la entrada que se le da para trabajar.

Complejidad espacial

La complejidad del espacio describe la cantidad de memoria y espacio de almacenamiento que necesita un algoritmo para completar la tarea que se le asigna.

Serie, Paralelo, Exacto y Aproximado

Los algoritmos pueden ser de naturaleza serial, de naturaleza paralela, producir resultados exactos o producir resultados aproximados. Algunos algoritmos pueden procesar datos en un proceso secuencial, lo que significa que son de naturaleza serial. Los algoritmos paralelos, por otro lado, pueden dividir los datos en partes más pequeñas y luego trabajar en cada una de ellas simultáneamente. Un algoritmo puede ser exacto o aproximado. El tipo exacto produce un valor predecible conocido cada vez que se ejecuta. Un algoritmo aproximado intenta encontrar una respuesta que podría ser exacta o no. A veces, los algoritmos ejecutarán cada paso con una decisión exacta. Esto se conoce como algoritmo determinista. Un algoritmo también puede intentar producir una solución utilizando sucesivas suposiciones, que se vuelven más precisas con el tiempo. Este tipo de algoritmo se conoce como no determinista.


Algoritmo de Euclides

Encontrar el máximo común denominador de dos números es una tarea común. Podemos escribir un programa de Python para completar esta tarea usando el algoritmo de Euclid. El máximo común denominador de dos números es el entero más grande que divide ambos números sin dejar residuo. Considere que tenemos num1 y num2. La forma en que funciona el algoritmo es dividir num1 por num2 y luego mirar el resto. Para esto, podemos usar el operador de módulo. Si el resto es cero, nos detenemos porque encontramos el máximo común denominador. De lo contrario, establecemos num1 en num2, y luego num2 en el resto, y repetimos en el paso uno hasta que el resto sea cero. Aquí está en Python.

3
5

Rendimiento del algoritmo Big-O

La notación Big-O es lo que se utiliza para describir el rendimiento del algoritmo. Describe el rendimiento del algoritmo a medida que el tamaño de la entrada crece con el tiempo. La letra O se utiliza porque la tasa de crecimiento de la complejidad temporal de un algoritmo también se denomina orden de operación. Las estructuras de datos a menudo pueden realizar múltiples tipos de operaciones como insertar o buscar valores. Cada uno puede tener su propio orden de funcionamiento.

Algunos términos comunes de Big-O

NotaciónDescripciónEjemplo
O (1)Tiempo constanteBuscando un solo elemento en una matriz
O (log n)LogarítmicoEncontrar un elemento en una matriz ordenada con una búsqueda binaria
En)Tiempo linealBuscando una matriz no insertada para un valor específico
O (n log n)Log-linealAlgoritmos de clasificación complejos como clasificación por pila y combinación
O (n 2 )CuadráticoClasificación simple como clasificación de burbujas, clasificación de selección y clasificación de inserción

En la tabla anterior hay algunos términos de Big-O en orden ascendente de complejidad temporal. Comienza con un tiempo constante , que tiene un Big-O de uno. Esto significa que la operación en cuestión no depende del número de elementos en el conjunto de datos dado. Un ejemplo puede ser verificar si un número es par o impar, o buscar un índice de elemento específico en una matriz. Entonces tenemos log n también conocido como tiempo logarítmico. Encontrar un valor en una matriz ordenada mediante una búsqueda binaria es un ejemplo de tiempo logarítmico. El siguiente es el tiempo lineal que corresponde a un Big-O de n. Un ejemplo de esto es buscar un elemento en una matriz sin clasificar. El último en nuestra tabla es el orden de n al cuadrado, que se denomina complejidad de tiempo cuadrático. Esto significa que a medida que aumenta el número de elementos en el conjunto de datos, el tiempo que lleva procesarlos aumenta en el cuadrado de ese número, por lo que no es tan eficiente.


Lista de los mejores algoritmos de programación

Aquí hay una lista de los algoritmos de programación más comunes que puede encontrar.

  • Algoritmo de ordenación por inserción La ordenación por inserción es un algoritmo de ordenación básico que construye la matriz o lista ordenada final un elemento a la vez.
  • Algoritmo de clasificación por selección Un algoritmo en el lugar donde la lista se divide en dos partes, la parte ordenada en el extremo izquierdo y la parte sin clasificar en el derecho.
  • Algoritmo de clasificación de burbujas recorre iterativamente la lista y compara elementos adyacentes intercambiándolos si están en el orden incorrecto.
  • Merge Sort Algorithm Un enfoque de divide y vencerás que fue inventado por John von Neumann en 1945
  • Algoritmo de ordenación rápida Una ordenación de comparación que puede ordenar elementos de cualquier tipo para los que se define una relación "menor que".
  • Algoritmo de búsqueda binaria Compara un valor objetivo con el elemento central de la matriz.
  • Algoritmo de búsqueda primero en amplitud Se utiliza para buscar estructuras de datos de árbol o gráfico. Comienza en la raíz del árbol y explora todos los nodos hermanos en la profundidad actual antes de pasar a los nodos en el siguiente nivel de profundidad.
  • Algoritmo de búsqueda de profundidad primero Comienza en el nodo raíz y explora lo más lejos posible a lo largo de cada rama antes de retroceder.
  • Ruta más corta en un algoritmo de laberinto Continúe siguiendo la ruta actual hasta llegar a un cruce cuando se tome una decisión aleatoria sobre la siguiente dirección a seguir.
  • Algoritmo de relleno de inundación Algoritmo Se utiliza para determinar un área delimitada conectada a un nodo dado en una matriz multidimensional.
  • Algoritmo de detección de ciclo de Floyd Un algoritmo de puntero que utiliza solo dos punteros, que se mueven a través de la secuencia a diferentes velocidades.
  • Algoritmo de Kadane Un enfoque dinámico para resolver el problema de “los elementos contiguos más grandes de una matriz”.
  • Algoritmo de subsecuencia creciente más larga Encuentra una subsecuencia de una secuencia particular donde los elementos de la subsecuencia están ordenados, de menor a mayor, y donde la subsecuencia es lo más larga posible.
  • Algoritmo de recorrido de árbol en orden, preorden, posorden Una forma de recorrido de gráfico y se refiere al proceso de visitar cada nodo en una estructura de datos de árbol, exactamente una vez.
  • Algoritmo de ordenación de pila Heapsort se puede considerar como una ordenación de selección mejorada basada en comparación
  • Algoritmo de búsqueda de unión Una estructura de datos de conjuntos disjuntos que rastrea un conjunto de elementos agrupados en varios subconjuntos disjuntos.
  • Algoritmo de Kruskal Un algoritmo de árbol de expansión mínimo que encuentra un borde del menor peso posible que conecta dos árboles cualesquiera en el bosque.
  • Algoritmo de Dijkstra Se utiliza para encontrar las rutas más cortas entre los nodos de un árbol o gráfico.
  • Algoritmo de Floyd Warshall Se utiliza para encontrar la ruta más corta en un gráfico ponderado con pesos de borde positivos o negativos.

¿Cuáles son algunos algoritmos de programación comunes? Resumen

En este tutorial, analizamos una descripción general de varios algoritmos en informática. Hay libros enteros dedicados a este tema, por lo que aunque no podemos cubrir cada algoritmo en profundidad aquí, proporcionamos enlaces útiles a cada uno de los algoritmos más comunes en informática. Otro gran recurso para algoritmos se puede encontrar en Khan Academy, donde cubren búsqueda binaria, notación asintótica, ordenación por selección, ordenación por inserción, algoritmos recursivos, torres de Hanoi, ordenación por fusión, ordenación rápida, representación de gráficos y búsqueda en amplitud.


Publicar un comentario

0 Comentarios