En matemáticas e informática, un algoritmo AL-gə-ridh-əm) es una especificación inequívoca de cómo resolver una clase de problemas. Los algoritmos pueden realizar tareas de cálculo, procesamiento de datos y razonamiento automático.

Como método eficaz, un algoritmo se puede expresar dentro de una cantidad finita de espacio y tiempo y en un lenguaje formal bien definido para calcular una función. Comenzando por un estado inicial y una entrada inicial (quizás vacía), las instrucciones describen un cálculo que, cuando se ejecuta, avanza a través de un número finito de estados sucesivos bien definidos, produciendo eventualmente «salida» y terminando en un estado final final. La transición de un estado a otro no es necesariamente determinista; algunos algoritmos, conocidos como algoritmos aleatorios, incorporan entrada aleatoria.

El concepto de algoritmo ha existido durante siglos y el uso del concepto se puede atribuir a los matemáticos griegos, por ejemplo, el tamiz de Eratóstenes y el algoritmo de Euclides; el término algoritmo en sí se deriva del matemático del siglo IX Muḥammad ibn Mūsā al’Khwārizmī, latinizado ‘Algoritmi’. Una formalización parcial de lo que se convertiría en la noción moderna de algoritmo comenzó con intentos de resolver el Entscheidungsproblem (el «problema de decisión») planteado por David Hilbert en 1928. Las formalizaciones posteriores se enmarcaron como intentos de definir «calculabilidad efectiva» o «método efectivo» ; esas formalizaciones incluyeron las funciones recursivas de Gödel-Herbrand-Kleene de 1930, 1934 y 1935, el cálculo lambda de la Iglesia Alonzo de 1936, la Formulación 1 de 1936 de Emil Post y las máquinas de Turing de Alan Turing de 1936-7 y 1939.

Etimología
La palabra «algoritmo» tiene sus raíces en latinizar el nombre de Muhammad ibn Musa al-Khwarizmi en un primer paso hacia el algoritmo. Al-Khwārizmī (persa: خوارزمی, hacia 780-850) fue un matemático, astrónomo, geógrafo y erudito persa de la Casa de la Sabiduría en Bagdad, cuyo nombre significa «el nativo de Khwarezm», una región que formaba parte de Gran Irán y ahora está en Uzbekistán.

Alrededor de 825, al-Khwarizmi escribió un tratado en árabe sobre el sistema numérico hindú-árabe, que fue traducido al latín en el siglo XII bajo el título Algoritmi de numero Indorum. Este título significa «Algoritmi en los números de los indios», donde «Algoritmi» era la latinización del traductor del nombre de Al-Khwarizmi. Al-Khwarizmi fue el matemático más leído en Europa a finales de la Edad Media, principalmente a través de otro de sus libros, el Álgebra. En latín medieval tardío, algorismus, ‘algorismo’ inglés, la corrupción de su nombre, simplemente significaba el «sistema decimal de números». En el siglo XV, bajo la influencia de la palabra griega ἀριθμός ‘número’ (véase ‘aritmética’), la palabra latina fue alterada a algorithmo, y el término inglés correspondiente ‘algoritmo’ se atestigua por primera vez en el siglo XVII; el sentido moderno fue introducido en el siglo XIX.

En inglés, fue utilizado por primera vez alrededor de 1230 y luego por Chaucer en 1391. El inglés adoptó el término francés, pero no fue hasta finales del siglo XIX que el «algoritmo» adquirió el significado que tiene en el inglés moderno.

Otro uso temprano de la palabra es desde 1240, en un manual titulado Carmen de Algorismo compuesto por Alexandre de Villedieu. Comienza así:

Haec algorismus ars praesens dicitur, en qua / Talibus Indorum fruimur bis quinque figuris.

que se traduce como:

El algoritmo es el arte por el cual actualmente utilizamos esas figuras indias, que son dos veces cinco.

El poema tiene unos pocos cientos de líneas y resume el arte de calcular con el nuevo estilo de dados indios, o Talibus Indorum, o números hindúes.

Definición informal
Para una presentación detallada de los diversos puntos de vista sobre la definición de «algoritmo», ver caracterizaciones de Algoritmo.
Una definición informal podría ser «un conjunto de reglas que define con precisión una secuencia de operaciones». que incluiría todos los programas de computadora, incluidos los programas que no realizan cálculos numéricos. En general, un programa es solo un algoritmo si finalmente se detiene.

Un ejemplo prototípico de un algoritmo es el algoritmo euclidiano para determinar el divisor común máximo de dos enteros; un ejemplo (hay otros) se describe en el diagrama de flujo anterior y como un ejemplo en una sección posterior.

Boolos, Jeffrey y 1974, 1999 ofrecen un significado informal de la palabra en la siguiente cita:

Ningún ser humano puede escribir lo suficientemente rápido, o suficientemente largo, o lo suficientemente pequeño † († «cada vez más pequeño sin límite … estaría tratando de escribir sobre moléculas, sobre átomos, sobre electrones») para enumerar todos los miembros de un enumerablemente infinito establecido escribiendo sus nombres, uno después del otro, en alguna notación. Pero los humanos pueden hacer algo igualmente útil, en el caso de ciertos conjuntos enumerablemente infinitos: pueden dar instrucciones explícitas para determinar el enésimo miembro del conjunto, para el n finito arbitrario. Tales instrucciones deben darse de manera bastante explícita, en una forma en la que puedan ser seguidas por una máquina de computación, o por un ser humano que sea capaz de llevar a cabo solo operaciones muy elementales de símbolos.

Un «conjunto enumerablemente infinito» es aquel cuyos elementos se pueden poner en correspondencia uno a uno con los enteros. Por lo tanto, Boolos y Jeffrey están diciendo que un algoritmo implica instrucciones para un proceso que «crea» números enteros de salida a partir de un entero arbitrario de «entrada» o enteros que, en teoría, pueden ser arbitrariamente grandes. Por lo tanto, un algoritmo puede ser una ecuación algebraica como y = m + n – dos «variables de entrada» arbitrarias myn que producen una salida y. Pero los intentos de varios autores para definir la noción indican que la palabra implica mucho más que esto, algo del orden de (para el ejemplo de adición):

Instrucciones precisas (en el lenguaje entendido por «la computadora») para un proceso rápido, eficiente y «bueno» que especifica los «movimientos» de «la computadora» (máquina o ser humano, equipado con la información y capacidades internas contenidas necesarias) para encontrar , decodificar y luego procesar enteros / símbolos de entrada arbitrarios myn, símbolos + y = … y producir «efectivamente», en un tiempo «razonable», entero-salida y y en un lugar específico y en un formato específico.
El concepto de algoritmo también se utiliza para definir la noción de decidability. Esa noción es central para explicar cómo se forman los sistemas formales a partir de un pequeño conjunto de axiomas y reglas. En lógica, el tiempo que un algoritmo requiere completar no se puede medir, ya que aparentemente no está relacionado con nuestra dimensión física habitual. A partir de tales incertidumbres, que caracterizan el trabajo en curso, surge la falta de disponibilidad de una definición de algoritmo que se adapte tanto al uso concreto (en cierto sentido) como abstracto del término.

Formalización
Los algoritmos son esenciales para la forma en que las computadoras procesan los datos. Muchos programas de computadora contienen algoritmos que detallan las instrucciones específicas que una computadora debe realizar (en un orden específico) para llevar a cabo una tarea específica, como calcular los cheques de pago de los empleados o imprimir boletas de calificaciones de los estudiantes. Por lo tanto, se puede considerar que un algoritmo es cualquier secuencia de operaciones que pueda ser simulada por un sistema Turing-complete. Los autores que afirman esta tesis incluyen Minsky (1967), Savage (1987) y Gurevich (2000):

Minsky: «Pero también mantendremos, con Turing … que cualquier procedimiento que pueda ser llamado» naturalmente «efectivo, de hecho puede ser realizado por una máquina (simple). Aunque esto puede parecer extremo, los argumentos … en su favor es difícil de refutar «.

Gurevich: «… el argumento informal de Turing a favor de su tesis justifica una tesis más fuerte: cada algoritmo puede ser simulado por una máquina de Turing … según Savage [1987], un algoritmo es un proceso computacional definido por una máquina de Turing» .

Típicamente, cuando un algoritmo está asociado con la información de procesamiento, los datos pueden leerse desde una fuente de entrada, escribirse en un dispositivo de salida y almacenarse para un procesamiento posterior. Los datos almacenados se consideran parte del estado interno de la entidad que realiza el algoritmo. En la práctica, el estado se almacena en una o más estructuras de datos.

Para algunos de estos procesos computacionales, el algoritmo debe estar rigurosamente definido: especificado en la forma en que se aplica en todas las circunstancias posibles que puedan surgir. Es decir, cualquier paso condicional debe tratarse sistemáticamente, caso por caso; los criterios para cada caso deben ser claros (y computables).

Debido a que un algoritmo es una lista precisa de pasos precisos, el orden del cálculo siempre es crucial para el funcionamiento del algoritmo. Generalmente, se supone que las instrucciones se enumeran explícitamente, y se describen como comenzando «desde arriba» y yendo «hacia abajo», una idea que se describe más formalmente por flujo de control.

Hasta ahora, esta discusión sobre la formalización de un algoritmo ha asumido las premisas de la programación imperativa. Esta es la concepción más común e intenta describir una tarea en medios discretos y «mecánicos». Único en esta concepción de algoritmos formalizados es la operación de asignación, que establece el valor de una variable. Se deriva de la intuición de «memoria» como un bloc de notas. Hay un ejemplo debajo de tal asignación.

Para algunas concepciones alternativas de lo que constituye un algoritmo, ver programación funcional y programación lógica.

Expresando algoritmos
Los algoritmos se pueden expresar en muchos tipos de notación, incluidos los lenguajes naturales, pseudocódigo, diagramas de flujo, diagramas de drakón, lenguajes de programación o tablas de control (procesados ​​por intérpretes). Las expresiones de algoritmos en lenguaje natural tienden a ser detalladas y ambiguas, y rara vez se usan para algoritmos complejos o técnicos. El pseudocódigo, los diagramas de flujo, los diagramas de drago y las tablas de control son formas estructuradas de expresar algoritmos que evitan muchas de las ambigüedades comunes en las declaraciones de lenguaje natural. Los lenguajes de programación están destinados principalmente a expresar algoritmos en una forma que pueda ser ejecutada por una computadora, pero a menudo se usan como una forma de definir o documentar algoritmos.

Existe una gran variedad de representaciones posibles y se puede expresar un programa de máquina de Turing dado como una secuencia de tablas de máquina (ver más en máquina de estado finito, tabla de transición de estado y tabla de control), como diagramas de flujo y tablas de drakon (ver más en diagrama de estado), o como una forma de código de máquina rudimentario o código de ensamblaje llamado «conjuntos de cuádruples» (ver más en la máquina de Turing).

Las representaciones de los algoritmos se pueden clasificar en tres niveles aceptados de la descripción de la máquina de Turing:

1 Descripción de alto nivel
«… en prosa para describir un algoritmo, ignorando los detalles de implementación. En este nivel no es necesario mencionar cómo la máquina gestiona su cinta o cabezal».
2 Descripción de la implementación
«… prosa utilizada para definir la forma en que la máquina de Turing utiliza su cabeza y la forma en que almacena datos en su cinta. En este nivel no damos detalles de los estados o la función de transición».
3 Descripción formal
El más detallado, el «nivel más bajo», da la «tabla de estados» de la máquina Turing.
Para ver un ejemplo del algoritmo simple «Agregar m + n» descrito en los tres niveles, vea Algoritmo # Ejemplos.

Implementación
La mayoría de los algoritmos están destinados a ser implementados como programas de computadora. Sin embargo, los algoritmos también se implementan por otros medios, como en una red neuronal biológica (por ejemplo, el cerebro humano que implementa la aritmética o un insecto que busca alimento), en un circuito eléctrico o en un dispositivo mecánico.

Algoritmos de computadora
En los sistemas informáticos, un algoritmo es básicamente una instancia de lógica escrita en el software por los desarrolladores de software para que sea efectiva para que la (s) computadora (s) «objetivo» deseada (s) produzcan salida a partir de una entrada determinada (tal vez nula). Un algoritmo óptimo, incluso funcionando en hardware antiguo, produciría resultados más rápidos que un algoritmo no óptimo (complejidad de tiempo más alta) para el mismo propósito, ejecutándose en un hardware más eficiente; es por eso que los algoritmos, como el hardware de la computadora, se consideran tecnología.

Programas «elegantes» (compactos), programas «buenos» (rápidos): la noción de «simplicidad y elegancia» aparece informalmente en Knuth y precisamente en Chaitin:

Knuth: «… queremos buenos algoritmos en algún sentido estético vagamente definido. Un criterio … es el tiempo que lleva realizar el algoritmo … Otros criterios son la adaptabilidad del algoritmo a las computadoras, su simplicidad y elegancia. , etc.
Chaitin: «… un programa es ‘elegante’, con lo cual quiero decir que es el programa más pequeño posible para producir el resultado que lo hace»
Chaitin introduce su definición con anterioridad: «Mostraré que no puede probar que un programa es ‘elegante'»; una prueba de este tipo resolvería el problema de la detención (ibid).

Algoritmo versus función computable por un algoritmo: para una función determinada, pueden existir múltiples algoritmos. Esto es cierto, incluso sin expandir el conjunto de instrucciones disponibles disponibles para el programador. Rogers observa que «es … importante distinguir entre la noción de algoritmo, es decir, el procedimiento y la noción de función computable por algoritmo, es decir, mapeo producido por procedimiento. La misma función puede tener varios algoritmos diferentes».

Desafortunadamente, puede haber una compensación entre bondad (velocidad) y elegancia (compacidad): un programa elegante puede tomar más pasos para completar un cálculo que uno menos elegante. Un ejemplo que usa el algoritmo de Euclides aparece a continuación.

Computadoras (y computors), modelos de computación: una computadora (o «computor» humano) es un tipo restringido de máquina, un «dispositivo mecánico determinista discreto» que sigue ciegamente sus instrucciones. Los modelos primitivos de Melzak y Lambek redujeron esta noción a cuatro elementos: (i) ubicaciones discretas y distinguibles, (ii) contadores discretos e indistinguibles (iii) un agente, y (iv) una lista de instrucciones que son efectivas con relación a la capacidad del agente.

Simulación de un algoritmo: lenguaje de computadora (computor): Knuth aconseja al lector que «la mejor forma de aprender un algoritmo es probarlo … inmediatamente tome papel y lápiz y trabaje con un ejemplo». Pero, ¿qué tal una simulación o ejecución de lo real? El programador debe traducir el algoritmo a un lenguaje que el simulador / computadora / computor pueda ejecutar efectivamente. Stone da un ejemplo de esto: al calcular las raíces de una ecuación cuadrática, el computor debe saber cómo tomar una raíz cuadrada. Si no lo hacen, entonces el algoritmo, para ser efectivo, debe proporcionar un conjunto de reglas para extraer una raíz cuadrada.

Esto significa que el programador debe conocer un «lenguaje» que sea efectivo en relación con el agente informático de destino (computadora / computor).

Análisis algorítmico
Con frecuencia es importante saber qué cantidad de un recurso en particular (como el tiempo o el almacenamiento) se requiere teóricamente para un algoritmo dado. Se han desarrollado métodos para el análisis de algoritmos para obtener tales respuestas cuantitativas (estimaciones); por ejemplo, el algoritmo de clasificación anterior tiene un requisito de tiempo de O (n), usando la notación O grande con n como la longitud de la lista. En todo momento, el algoritmo solo necesita recordar dos valores: el número más grande encontrado hasta el momento y su posición actual en la lista de entrada. Por lo tanto, se dice que tiene un requisito de espacio de O (1), si el espacio requerido para almacenar los números ingresados ​​no se cuenta, o O (n) si se cuenta.

Formal versus empírico
El análisis y el estudio de los algoritmos es una disciplina de la informática y, a menudo, se practica de forma abstracta sin el uso de un lenguaje de programación o implementación específicos. En este sentido, el análisis de algoritmo se asemeja a otras disciplinas matemáticas porque se centra en las propiedades subyacentes del algoritmo y no en los detalles de una implementación en particular. Por lo general, el pseudocódigo se usa para el análisis ya que es la representación más simple y general. Sin embargo, en última instancia, la mayoría de los algoritmos generalmente se implementan en plataformas de hardware / software particulares y su eficiencia algorítmica se pone a prueba con el uso de código real. Para la solución de un problema «único», la eficacia de un algoritmo en particular puede no tener consecuencias significativas (a menos que n sea extremadamente grande) pero para los algoritmos diseñados para un uso científico rápido interactivo, comercial o de larga duración puede ser crítico. Escalar desde n pequeño a n grande frecuentemente expone algoritmos ineficientes que de otra manera serían benignos.

Eficiencia de ejecución
Para ilustrar las posibles mejoras posibles incluso en algoritmos bien establecidos, una innovación significativa reciente, relacionada con los algoritmos FFT (utilizados en gran medida en el campo del procesamiento de imágenes), puede reducir el tiempo de procesamiento hasta 1,000 veces para aplicaciones como imágenes médicas. En general, las mejoras de velocidad dependen de las propiedades especiales del problema, que son muy comunes en las aplicaciones prácticas. Las aceleraciones de esta magnitud permiten que los dispositivos informáticos que hacen un uso extensivo del procesamiento de imágenes (como cámaras digitales y equipos médicos) consuman menos energía.

Clasificación
Hay varias formas de clasificar algoritmos, cada uno con sus propios méritos.

Por implementación
Una forma de clasificar los algoritmos es por medios de implementación.

Recursión
Un algoritmo recursivo es uno que invoca (hace referencia) a sí mismo repetidamente hasta que una determinada condición (también conocida como condición de terminación) coincide, que es un método común para la programación funcional. Los algoritmos iterativos usan construcciones repetitivas como bucles y, a veces, estructuras de datos adicionales como pilas para resolver los problemas dados. Algunos problemas son naturalmente adecuados para una implementación u otra. Por ejemplo, las torres de Hanoi se comprenden bien utilizando la implementación recursiva. Cada versión recursiva tiene una versión iterativa equivalente (pero posiblemente más o menos compleja), y viceversa.

Lógico
Un algoritmo puede verse como una deducción lógica controlada. Esta noción puede expresarse como: Algoritmo = lógica + control. El componente lógico expresa los axiomas que pueden usarse en el cálculo y el componente de control determina la forma en que se aplica la deducción a los axiomas. Esta es la base del paradigma de programación lógica. En los lenguajes de programación de lógica pura, el componente de control es fijo y los algoritmos se especifican suministrando solo el componente lógico. El atractivo de este enfoque es la semántica elegante: un cambio en los axiomas tiene un cambio bien definido en el algoritmo.

En serie, paralelo o distribuido
Los algoritmos generalmente se discuten con la suposición de que las computadoras ejecutan una instrucción de un algoritmo a la vez. Esas computadoras a veces se llaman computadoras seriales. Un algoritmo diseñado para dicho entorno se denomina algoritmo en serie, a diferencia de los algoritmos paralelos o los algoritmos distribuidos. Los algoritmos paralelos aprovechan arquitecturas de computadora donde varios procesadores pueden trabajar en un problema al mismo tiempo, mientras que los algoritmos distribuidos utilizan múltiples máquinas conectadas a una red informática. Los algoritmos paralelos o distribuidos dividen el problema en subproblemas más simétricos o asimétricos y reúnen los resultados nuevamente. El consumo de recursos en tales algoritmos no es solo ciclos de procesador en cada procesador sino también la sobrecarga de comunicación entre los procesadores. Algunos algoritmos de clasificación se pueden paralelizar de manera eficiente, pero su sobrecarga de comunicación es costosa. Los algoritmos iterativos son generalmente paralelizables. Algunos problemas no tienen algoritmos paralelos y se denominan problemas de serie inherentes.

Determinista o no determinista
Los algoritmos deterministas resuelven el problema con una decisión exacta en cada paso del algoritmo, mientras que los algoritmos no deterministas resuelven los problemas mediante la adivinación, aunque las conjeturas típicas se vuelven más precisas mediante el uso de la heurística.

Exacto o aproximado
Mientras que muchos algoritmos alcanzan una solución exacta, los algoritmos de aproximación buscan una aproximación más cercana a la verdadera solución. La aproximación se puede alcanzar utilizando una estrategia determinista o aleatoria. Tales algoritmos tienen un valor práctico para muchos problemas difíciles. Uno de los ejemplos de un algoritmo aproximado es el problema de Knapsack. El problema de Knapsack es un problema donde hay un conjunto de elementos determinados. El objetivo del problema es empacar la mochila para obtener el valor total máximo. Cada artículo tiene algún peso y algún valor. El peso total que podemos transportar no es más que un número fijo X. Por lo tanto, debemos considerar el peso de los artículos así como su valor.

Algoritmo cuántico
Funcionan con un modelo realista de computación cuántica. El término se usa generalmente para aquellos algoritmos que parecen intrínsecamente cuánticos o que utilizan alguna característica esencial de la computación cuántica, como la superposición cuántica o el enredo cuántico.

Por paradigma de diseño
Otra forma de clasificar los algoritmos es mediante su metodología de diseño o paradigma. Hay una cierta cantidad de paradigmas, cada uno diferente del otro. Además, cada una de estas categorías incluye muchos tipos diferentes de algoritmos. Algunos paradigmas comunes son:

Fuerza bruta o búsqueda exhaustiva
Este es el método ingenuo de probar todas las soluciones posibles para ver cuál es el mejor.

Divide y conquistaras
Un algoritmo de dividir y conquistar reduce repetidamente una instancia de un problema a una o más instancias más pequeñas del mismo problema (generalmente recursivamente) hasta que las instancias sean lo suficientemente pequeñas como para resolverlas fácilmente. Uno de esos ejemplos de divide y vencerás es la clasificación por fusión. La ordenación se puede hacer en cada segmento de datos después de dividir los datos en segmentos y la ordenación de datos completos se puede obtener en la fase de conquista fusionando los segmentos. Una variante más simple de dividir y conquistar se llama algoritmo de disminución y conquista, que resuelve un subproblema idéntico y utiliza la solución de este subproblema para resolver el problema mayor. Dividir y vencer divide el problema en múltiples subproblemas y, por lo tanto, la etapa de conquista es más compleja que los algoritmos de disminución y conquista. Un ejemplo de algoritmo de disminución y conquista es el algoritmo de búsqueda binaria.

Búsqueda y enumeración
Muchos problemas (como jugar al ajedrez) se pueden modelar como problemas en los gráficos. Un algoritmo de exploración de gráficos especifica reglas para moverse por un gráfico y es útil para tales problemas. Esta categoría también incluye algoritmos de búsqueda, enumeración de ramas y límites y retroceso.
Algoritmo aleatorizado

Reducción de la complejidad
Esta técnica implica resolver un problema difícil transformándolo en un problema mejor conocido para el cual tenemos (con suerte) algoritmos asintóticamente óptimos. El objetivo es encontrar un algoritmo reductor cuya complejidad no esté dominada por los algoritmos reducidos resultantes. Por ejemplo, un algoritmo de selección para encontrar la mediana en una lista desordenada implica primero clasificar la lista (la parte costosa) y luego extraer el elemento medio en la lista ordenada (la parte barata). Esta técnica también se conoce como transformar y conquistar.

Problemas de optimización
Para problemas de optimización hay una clasificación más específica de algoritmos; un algoritmo para tales problemas puede pertenecer a una o más de las categorías generales descritas anteriormente, así como a uno de los siguientes:

Programación lineal
Cuando se buscan soluciones óptimas para una función lineal ligada a restricciones lineales de igualdad y desigualdad, las restricciones del problema se pueden usar directamente para producir las soluciones óptimas. Existen algoritmos que pueden resolver cualquier problema en esta categoría, como el popular algoritmo simplex. Los problemas que se pueden resolver con programación lineal incluyen el problema de flujo máximo para gráficos dirigidos. Si un problema requiere además que una o más de las incógnitas debe ser un número entero, entonces se clasifica en una programación entera. Un algoritmo de programación lineal puede resolver dicho problema si se puede demostrar que todas las restricciones para valores enteros son superficiales, es decir, que las soluciones satisfacen estas restricciones de todos modos. En el caso general, se usa un algoritmo especializado o un algoritmo que encuentra soluciones aproximadas, dependiendo de la dificultad del problema.
Programación dinámica

Cuando un problema muestra que las subestructuras óptimas -es decir, la solución óptima para un problema puede construirse a partir de soluciones óptimas a subproblemas- y subproblemas superpuestos, es decir, los mismos subproblemas se usan para resolver muchas instancias de problemas diferentes, un enfoque más rápido llamado programación dinámica evita volver a calcular soluciones que ya han sido calculados. Por ejemplo, el algoritmo de Floyd-Warshall, el camino más corto hacia un objetivo desde un vértice en un gráfico ponderado, se puede encontrar utilizando la ruta más corta hacia el objetivo desde todos los vértices adyacentes. La programación dinámica y la memorización van de la mano. La diferencia principal entre programación dinámica y división y conquista es que los subproblemas son más o menos independientes en división y conquista, mientras que los subproblemas se superponen en la programación dinámica. La diferencia entre la programación dinámica y la recursión directa es en el almacenamiento en caché o la memorización de llamadas recursivas. Cuando los subproblemas son independientes y no hay repetición, la memorización no ayuda; por lo tanto, la programación dinámica no es una solución para todos los problemas complejos. Al utilizar la memorización o mantener una tabla de subproblemas ya resueltos, la programación dinámica reduce la naturaleza exponencial de muchos problemas a la complejidad polinómica.

El método codicioso
Un algoritmo codicioso es similar a un algoritmo de programación dinámica en el sentido de que funciona mediante el examen de las subestructuras, en este caso no del problema sino de una solución dada. Tales algoritmos comienzan con alguna solución, que se puede dar o se ha construido de alguna manera, y mejorarla haciendo pequeñas modificaciones. Para algunos problemas, pueden encontrar la solución óptima, mientras que para otros se detienen en óptimas locales, es decir, en soluciones que el algoritmo no puede mejorar, pero que no son óptimas. El uso más popular de los algoritmos codiciosos es encontrar el árbol de expansión mínimo donde encontrar la solución óptima es posible con este método. Huffman Tree, Kruskal, Prim, Sollin son algoritmos codiciosos que pueden resolver este problema de optimización.

El método heurístico
En los problemas de optimización, los algoritmos heurísticos se pueden utilizar para encontrar una solución cercana a la solución óptima en los casos en que no es práctico encontrar la solución óptima. Estos algoritmos funcionan acercándose cada vez más a la solución óptima a medida que avanzan. En principio, si se ejecutan durante un tiempo infinito, encontrarán la solución óptima. Su mérito es que pueden encontrar una solución muy cercana a la solución óptima en un tiempo relativamente corto. Dichos algoritmos incluyen búsqueda local, búsqueda tabú, recocido simulado y algoritmos genéticos. Algunos de ellos, como el recocido simulado, son algoritmos no deterministas, mientras que otros, como la búsqueda tabú, son deterministas. Cuando se conoce un límite en el error de la solución no óptima, el algoritmo se categoriza además como un algoritmo de aproximación.

Por campo de estudio
Cada campo de la ciencia tiene sus propios problemas y necesita algoritmos eficientes. Los problemas relacionados en un campo a menudo se estudian juntos. Algunas clases de ejemplo son algoritmos de búsqueda, algoritmos de clasificación, algoritmos de fusión, algoritmos numéricos, algoritmos de gráficos, algoritmos de cadenas, algoritmos geométricos computacionales, algoritmos combinatorios, algoritmos médicos, aprendizaje automático, criptografía, algoritmos de compresión de datos y técnicas de análisis sintáctico.

Los campos tienden a superponerse entre sí, y los avances de algoritmo en un campo pueden mejorar los de otros campos, a veces completamente no relacionados. Por ejemplo, la programación dinámica se inventó para la optimización del consumo de recursos en la industria, pero ahora se usa para resolver una amplia gama de problemas en muchos campos.

Por complejidad
Los algoritmos se pueden clasificar por la cantidad de tiempo que necesitan completar en comparación con su tamaño de entrada:

Tiempo constante: si el tiempo que necesita el algoritmo es el mismo, independientemente del tamaño de la entrada. Por ejemplo, un acceso a un elemento de matriz.
Tiempo lineal: si el tiempo es proporcional al tamaño de entrada. Por ejemplo, el recorrido de una lista.
Tiempo logarítmico: si el tiempo es una función logarítmica del tamaño de entrada. Ej. Algoritmo de búsqueda binaria.
Tiempo polinomial: si el tiempo es una potencia del tamaño de entrada. Por ejemplo, el algoritmo de ordenación de burbujas tiene una complejidad de tiempo cuadrática.
Tiempo exponencial: si el tiempo es una función exponencial del tamaño de entrada. Ej. Búsqueda de fuerza bruta.
Algunos problemas pueden tener múltiples algoritmos de diferente complejidad, mientras que otros problemas pueden no tener algoritmos o ningún algoritmo eficiente conocido. También hay asignaciones de algunos problemas a otros problemas. Debido a esto, se encontró que era más adecuado clasificar los problemas en sí mismos en lugar de los algoritmos en clases de equivalencia en función de la complejidad de los mejores algoritmos posibles para ellos.

Algoritmos continuos
El adjetivo «continuo» cuando se aplica a la palabra «algoritmo» puede significar:

Algoritmo que opera en datos que representan cantidades continuas, aunque estos datos están representados por aproximaciones discretas; dichos algoritmos se estudian en análisis numérico; o
Un algoritmo en forma de ecuación diferencial que opera continuamente en los datos, ejecutándose en una computadora analógica.