algoritm

Vista previa del material en texto

Universidad Dominicana O&M 
 
Nombre: 
Luis Mario Ramírez Spencer 
Matricula: 
23-EIST-6-001 
Sección: 
311 
Asignatura: 
[506310] ALGORITMOS COMPUTACIONALES 
Docente 
Felipe Arturo Durán Rodríguez 
Fecha: 
27/10/2023 
 
 
 
 
 
Introducción: 
El análisis de algoritmos es una disciplina fundamental en la ciencia de la computación que 
busca comprender y evaluar el rendimiento de los algoritmos en términos de tiempo y espacio. 
En otras palabras, se enfoca en responder preguntas clave como: ¿cuánto tiempo tomará un 
algoritmo para procesar una entrada de tamaño dado? ¿Cuánta memoria requerirá? ¿Cómo se 
compara su eficiencia con otros algoritmos en el mismo problema? El análisis de algoritmos es 
esencial para garantizar que las soluciones tecnológicas sean efectivas y escalables. 
Este trabajo de investigación tiene como objetivo explorar en profundidad el análisis de 
algoritmos, desglosando sus conceptos fundamentales, técnicas y aplicaciones. Examinaremos la 
importancia del análisis de algoritmos en el desarrollo de software, la toma de decisiones 
empresariales y la optimización de sistemas informáticos. También abordaremos cuestiones clave 
relacionadas con la complejidad computacional, la notación "Big O" y las estrategias de diseño 
de algoritmos. 
A medida que avanzamos en la era de la información, el conocimiento sólido del análisis de 
algoritmos se vuelve más esencial que nunca. Este trabajo servirá como una guía integral para 
comprender y aplicar eficazmente este campo de estudio, y nos ayudará a apreciar la influencia 
de los algoritmos en nuestra vida diaria, desde la velocidad de nuestras búsquedas en línea hasta 
la eficiencia de nuestras redes sociales. 
 
Tema III. Análisis de Algoritmo 
Análisis de Algoritmo: 
En el análisis teórico de algoritmos, es común estimar su complejidad en el sentido asintótico, es 
decir, estimar la función de complejidad para entradas arbitrariamente grandes. El término 
«análisis de algoritmos» fue acuñado por Donald Knuth. 
El análisis de algoritmos es una parte importante de la teoría de la complejidad computacional, 
que proporciona una estimación teórica de los recursos necesarios de un algoritmo para resolver 
un problema computacional específico. La mayoría de los algoritmos están diseñados para trabajar 
con entradas de longitud arbitraria. El análisis de algoritmos es la determinación de la cantidad de 
recursos de tiempo y espacio necesarios para ejecutarlo. 
Por lo general, la eficiencia o el tiempo de ejecución de un algoritmo se establece como una función 
que relaciona la longitud de entrada con el número de pasos, conocido como complejidad de 
tiempo o volumen de memoria, conocido como complejidad de espacio. 
El análisis de algoritmos es una herramienta para hacer la evaluación del diseño de un algoritmo, 
permite establecer la calidad de un programa y compararlo con otros que puedan resolver el mismo 
problema, sin necesidad de desarrollarlos. El análisis de algoritmos estudia, desde un punto de 
vista teórico, los recursos computacionales que requiere la ejecución de un programa, es decir su 
eficiencia (tiempo de CPU, uso de memoria, ancho de banda, ...). Además de la eficiencia en el 
desarrollo de software existen otros factores igualmente relevantes: funcionalidad, corrección, 
robustez, usabilidad, modularidad, mantenibilidad, fiabilidad, simplicidad y aún el propio costo de 
programación. 
El análisis de algoritmos se basa en: 
• El análisis de las características estructurales del algoritmo que respalda el programa. 
• La cantidad de memoria que utiliza para resolver un problema. 
• La evaluación del diseño de las estructuras de datos del programa, midiendo la eficiencia 
de los algoritmos para resolver el problema planteado. 
Determinar la eficiencia de un algoritmo nos permite establecer lo que es factible en la 
implementación de una solución de lo que es imposible. 
- Tipos de Análisis: 
• Peor caso (usualmente): T(n) = Tiempo máximo necesario para un problema de tamaño n. 
• Caso medio (a veces): T(n) = Tiempo esperado para un problema cualquiera de tamaño n. 
(Requiere establecer una distribución estadística) 
• Mejor caso (engañoso): T(n) = Tiempo menor para un problema cualquiera de tamaño n. 
Los criterios para evaluar programas son diversos: eficiencia, portabilidad, eficacia, robustez, etc. 
El análisis de complejidad está relacionado con la eficiencia del programa. La eficiencia mide el 
uso de los recursos del computador por un algoritmo. Por su parte, el análisis de complejidad mide 
el tiempo de cálculo para ejecutar las operaciones (complejidad en tiempo) y el espacio de memoria 
para contener y manipular el programa más los datos (complejidad en espacio). Así, el objetivo 
del análisis de complejidad es cuantificar las medidas físicas: tiempo de ejecución y espacio de 
memoria y comparar distintos algoritmos que resuelven un mismo problema. 
El tiempo de ejecución debe definirse como una función que depende de la entrada; en particular, 
de su tamaño. El tiempo requerido por un algoritmo expresado como una función del tamaño de 
la entrada del problema se denomina complejidad en tiempo del algoritmo y se denota T(n). El 
comportamiento límite de la complejidad a medida que crece el tamaño del problema se denomina 
complejidad en tiempo asintótica. De manera análoga se pueden establecer definiciones para la 
complejidad en espacio y la complejidad en espacio asintótica. 
El tiempo de ejecución depende de diversos factores. Se tomará como más relevante el relacionado 
con la entrada de datos del programa, asociando a un problema un entero llamado tamaño del 
problema, el cual es una medida de la cantidad de datos de entrada. 
El término análisis de algoritmos fue acuñado por Donald Knuth1 y se refiere al proceso de 
encontrar la complejidad computacional de un algoritmo que resuelva un problema 
computacional dado, con el objetivo de proveer estimaciones teóricas de los recursos que necesita. 
Usualmente, los recursos a los cuales se hace referencia son el tiempo (complejidad temporal) y el 
almacenamiento (complejidad espacial). Mientras que la complejidad temporal involucra 
determinar una función que relaciona la longitud o el tamaño de la entrada del algoritmo con el 
número de pasos que realiza, la complejidad espacial busca la cantidad de ubicaciones de 
almacenamiento que utiliza. Distintos algoritmos pueden utilizarse para resolver un mismo 
problema y a su vez los algoritmos pueden estudiarse de forma independiente del lenguaje de 
programación a utilizar y de la máquina donde se ejecutará.2 Esto significa que se necesitan 
técnicas que permitan comparar la eficiencia de los algoritmos antes de su implementación. 
El análisis algorítmico es una técnica utilizada en la ciencia de la computación para evaluar la 
eficiencia de los algoritmos. En el contexto de las estructuras de datos, el análisis algorítmico se 
utiliza para evaluar cuánto tiempo y espacio se requieren para realizar operaciones en la estructura 
de datos. 
Una técnica común utilizada en el análisis algorítmico es la notación “Big O”. Esta notación 
describe la tasa de crecimiento del tiempo o del espacio requerido a medida que el tamaño del 
problema aumenta. Por ejemplo, un algoritmo con una complejidad de O(n) requerirá 
aproximadamente n operaciones para un problema de tamaño n. Un algoritmo con una 
complejidad de O(n^2) requerirá aproximadamente n^2 operaciones para un problema de tamaño 
n. 
La elección adecuada de la estructura de datos y el algoritmo es clave para optimizar tanto el 
tiempo como el espacio requerido al resolver un problema computacional. Por ejemplo, si se 
necesita realizar una gran cantidad de búsquedas en una estructura de datos, es importante elegir 
una estructura de datos que permita búsquedas eficientes, como un árbol de búsqueda binario. Si 
se necesita realizar muchas inserciones y eliminacionesen la estructura de datos, es importante 
elegir una estructura de datos que permita inserciones y eliminaciones eficientes, como una lista 
enlazada. 
https://es.wikipedia.org/wiki/Donald_Knuth
https://es.wikipedia.org/wiki/An%C3%A1lisis_de_algoritmos#cite_note-1
https://es.wikipedia.org/wiki/Algoritmo
https://es.wikipedia.org/wiki/Problema_computacional
https://es.wikipedia.org/wiki/Problema_computacional
https://es.wikipedia.org/wiki/An%C3%A1lisis_de_algoritmos#cite_note-2
Recursos del Computador y Complejidad 
En muchos casos, la complejidad de tiempo de un algoritmo es igual para todas las instancias de 
tamaño n del problema. En otros casos, la complejidad de un algoritmo de tamaño n es distinta 
dependiendo de las instancias de tamaño n del problema que resuelve. Esto nos lleva a estudiar la 
complejidad del peor caso, mejor caso, y caso promedio. 
Para un tamaño dado (n), la complejidad del algoritmo en el peor caso resulta de tomar el máximo 
tiempo (complejidad máxima) en que se ejecuta el algoritmo, entre todas las instancias del 
problema (que resuelve el algoritmo) de tamaño n; la complejidad en el caso promedio es la 
esperanza matemática del tiempo de ejecución del algoritmo para entradas de tamaño n, y la 
complejidad mejor caso es el menor tiempo en que se ejecuta el algoritmo para entradas de tamaño 
n. Por defecto se toma la complejidad del peor caso como medida de complejidad T(n) del 
algoritmo. 
Aún cuando son los programas que los llegan realmente a consumir recursos computacionales 
(memoria, tiempo, etc.) sobre una máquina concreta, se realiza el análisis sobre el algoritmo de 
base, considerando que se ejecuta en una máquina hipotética. 
La complejidad de un programa depende de: 
• La máquina y el compilador utilizados 
• El tamaño de los datos de entrada que depende del tipo de datos y del algoritmo 
• El valor de los datos de entrada. 
Complejidad temporal: Se define como el tiempo que tarda un algoritmo en una entrada de 
tamaño n. 
La complejidad en el caso peor proporciona una medida pesimista, pero fiable. 
Dado que se realiza un estudio teórico de la complejidad, ignorando aspectos como las 
características de la máquina y el compilador, se tiene en cuenta que las diferencias en eficiencia 
se hacen más significativos para tamaños grandes de los datos de entrada se analiza la complejidad 
en términos de su comportamiento asintótico, dejando de lado la forma exacta de la función de 
complejidad. 
¿De qué hablamos cuando hablamos de complejidad? Resulta evidente que el tiempo real 
requerido por una computadora para la ejecución de algoritmo es directamente proporcional al 
número de operaciones básicas que la computadora debe realizar en su ejecución. Medir por lo 
tanto el tiempo real de ejecución equivale a medir el número de operaciones elementales 
realizadas. Desde ahora supondremos que todas las operaciones básicas se ejecutan en una unidad 
de tiempo. Por esta razón se suele llamar tiempo de ejecución no al tiempo real físico, sino al 
número de operaciones elementales realizadas. Otro de los factores importantes, en ocasiones 
decisivo, para comparar algoritmos es la cantidad de memoria del computador requerida para 
almacenar los datos durante el proceso. La cantidad de memoria utilizada durante el proceso se 
suele llamar espacio requerido por el algoritmo. 
Al no ser única la manera de representar un algoritmo mediante un programa, y al no ser único el 
computador en el cual se ejecutará, resulta que la medida del tiempo será variable dependiendo 
fundamentalmente de los siguientes factores: 
1) El lenguaje de programación elegido 
2) El programa que representa 
3) El computador que lo ejecuta 
Por eso surge la necesidad de medir el tiempo requerido por un algoritmo independientemente de 
su representación y del computador que lo ejecute. 
El análisis de algoritmos se encarga del estudio del tiempo y espacio requerido por un algoritmo 
para su ejecución. Ambos parámetros pueden ser estudiados con respecto al peor caso (también 
conocido como caso general) o respecto al caso probabilístico (o caso esperado). 
En Ciencias de la Computación, el término eficiencia algorítmica es usado para describir aquellas 
propiedades de los algoritmos que están relacionadas con la cantidad de recursos utilizados por el 
algoritmo. Un algoritmo debe ser analizado para determinar el uso de los recursos que realiza. La 
eficiencia algorítmica puede ser vista como análogo a la ingeniería de productividad de un proceso 
repetitivo o continuo. 
Con el objetivo de lograr una eficiencia máxima se quiere minimizar el uso de recursos. Sin 
embargo, varias medidas (complejidad temporal, complejidad espacial) no pueden ser comparadas 
directamente, luego, cual de dos algoritmos es considerado más eficiente, depende de cual medida 
de eficiencia se está considerando como prioridad; por ejemplo la prioridad podría ser obtener la 
salida del algoritmo lo más rápido posible, o que minimice el uso de la memoria, o alguna otra 
medida particular. 
Una diferencia significativa entre el análisis de complejidad de algoritmos y la teoría de la 
complejidad computacional, es que el primero se dedica a determinar la cantidad de recursos 
requeridos por un algoritmo en particular para resolver un problema, mientras que la segunda, 
analiza todos los posibles algoritmos que pudieran ser usados para resolver el mismo problema. 
La importancia de la eficiencia con respecto a la complejidad temporal fue enfatizada por Ada 
Lovelace en 1843 como resultado de su trabajo con el motor analítico mecánico de Charles 
Babbage: «En casi todo cómputo son posibles una gran variedad de configuraciones para la 
sucesión de un proceso, y varias consideraciones pueden influir en la selección de estas según el 
propósito de un motor de cálculos. Un objetivo esencial es escoger la configuración que tienda a 
minimizar el tiempo necesario para completar el cálculo.» 
Existen muchas maneras para medir la cantidad de recursos utilizados por un algoritmo: las dos 
medidas más comunes son la complejidad temporal y espacial; otras medidas a tener en cuenta 
podrían ser la velocidad de transmisión, uso temporal del disco duro, así como uso del mismo a 
largo plazo, consumo de energía, tiempo de respuesta ante los cambios externos, etc. Muchas de 
estas medidas dependen del tamaño de la entrada del algoritmo (Ej. la cantidad de datos a ser 
procesados); además podrían depender de la forma en que los datos están organizados (Ej. 
algoritmos de ordenación necesitan hacer muy poco en datos que ya están ordenados o que están 
ordenados de forma inversa). 
En la práctica existen otros factores que pueden afectar la eficiencia de un algoritmo, tales como 
la necesidad de cierta precisión y/o veracidad. La forma en que un algoritmo es implementado 
también puede tener un efecto de peso en su eficiencia, muchos de los aspectos asociados a la 
implementación se vinculan a problemas de optimización. 
Estudio de la Complejidad de un algoritmo: 
La complejidad de un algoritmo es una medida de cuán eficiente es el algoritmo para resolver el 
problema. En otras palabras, es una medida de cuánto tiempo y espacio (memoria) requiere el 
algoritmo para producir una solución. 
En matemáticas, la complejidad se estudia a menudo en el contexto de los algoritmos. Esto se debe 
a que muchos problemas matemáticos se pueden resolver mediante algoritmos, y la eficiencia de 
estos algoritmos es un factor importante en su utilidad en la práctica. 
Hay varias formas de medir la complejidad de un algoritmo. Uno de los más comunes es contar el 
número de operaciones básicas (como sumas o multiplicaciones) que realiza el algoritmo. Esto se 
conoce como la complejidad temporal del algoritmo. 
Otra forma de medir la complejidad es 
contar la cantidad de memoria (en bytes 
o bits) que requiere el algoritmo. Esto 
se conoce como la complejidad espacialdel algoritmo. 
Las complejidades de tiempo y espacio 
de un algoritmo se pueden expresar 
utilizando la notación O grande. Esta 
notación proporciona una forma de 
comparar la complejidad de diferentes 
algoritmos. Por ejemplo, un algoritmo 
con una complejidad temporal de O(n) 
se considera más eficiente que un 
algoritmo con una complejidad 
temporal de O(n^2), porque crece a un ritmo más lento a medida que aumenta el tamaño de entrada. 
En general, el objetivo del diseño de algoritmos es encontrar algoritmos que sean eficientes y 
fáciles de implementar. Esto implica un compromiso entre la complejidad del tiempo y el 
espacio, así como otros factores como la simplicidad y la mantenibilidad. 
En general, el estudio de la complejidad de los algoritmos es una parte importante tanto de las 
matemáticas como de la informática. Nos ayuda a comprender las limitaciones de los algoritmos 
y las compensaciones involucradas en la resolución de problemas complejos. 
El valor ya no está en hacer un programa que realice cierta tarea, porque probablemente haya una 
IA que pueda diseñarte un código para esa cierta tarea en un tiempo extremadamente bajo, pero 
si tiene un valor añadido que nosotros podamos optimizar ese algoritmo para mejorar sus 
tiempos de ejecución y costes computacionales. 
Un algoritmo será más eficiente comparado con otro, siempre que consuma menos recursos, como 
el tiempo y espacio de memoria necesarios para ejecutarlo. 
 
1. Complejidad Temporal: Tiempo de cómputo necesario para ejecutar algún programa. 
2. Complejidad Espacial: Memoria que utiliza un programa para su ejecución, indica la cantidad 
de espacio requerido para ejecutar el algoritmo; es decir, el espacio en memoria que ocupan todas 
las variables propias al algoritmo. Para calcular la memoria estática de un algoritmo se suma la 
memoria que ocupan las variables declaradas en el algoritmo. Para el caso de la memoria dinámica, 
el cálculo no es tan simple ya que, este depende de cada ejecución del algoritmo. 
Nosotros estudiaremos las complejidades temporales, con este fin, para cada problema 
determinaremos una medida N, que llamaremos tamaño de la entrada o número de datos a procesar 
por el programa, intentaremos hallar respuestas en función de dicha N. 
Esto dependerá de la naturaleza del problema, por ejemplo, si hablamos de un arreglo se puede ver 
a N como el rango del arreglo, para una matriz, el número de elementos que la componen; para un 
grafo, podría ser el número de nodos o arcos, no se puede establecer una regla para N, pues cada 
problema tiene su propia complejidad. 
Medidas Asintomáticas 
Una medida asintótica es un conjunto de funciones que muestran un comportamiento similar 
cuando los argumentos toman valores muy grandes. Las medidas asintóticas se definen en términos 
de una función de referencia f. 
Tanto las funciones de complejidad, T, como las funciones de referencia de las medidas asintóticas, 
f, presentan el perfil T, f : ℵ → ℜ+ donde ℵ es el dominio del tamaño de los datos y ℜ+ el valor 
del coste del algoritmo. 
Definimos la medida asintótica de cota superior f, que notaremos O (f) como el conjunto de 
funciones { T | existen c ∈ ℜ+ , n0 ∈ ℵ tales que, para todo n ≥ n0, T(n) ≤ c ⋅ f(n) } Si T ∈ O( f ) 
decimos que “T(n) es del orden de f(n)” y que “f es asintóticamente una cota superior del 
crecimiento de T”. 
Definimos la medida asintótica de cota inferior f, que notaremos Ω (f) como el conjunto de 
funciones { T | existen c ∈ℜ+ , n0 ∈ ℵ tales que, para todo n ≥ n0, T(n) ≥ c ⋅ f(n) } Si T ∈ Ω( f ) 
podemos decir que “f es asintóticamente una cota inferior del crecimiento de T”. 
Definimos la medida asintótica exacta f, que notaremos Θ (f) como el conjunto de funciones { T | 
existen c1, c2 ∈ ℜ+ , n0 ∈ ℵ, tales que, para todo n ≥ n0, c1 ⋅ f(n) ≤ T(n) ≤ c2 ⋅ f(n) } Si T ∈ Θ( f 
) decimos que “T(n) es del orden exacto de f(n)”. 
Una vez vista la forma de calcular el tiempo de ejecución T de un algoritmo, se debe intentar 
clasificar dichas funciones de forma que sea posible compararlas. Para ello, existen clases de 
equivalencia, correspondientes a las funciones que “crecen de la misma forma”. 
Cota Superior. Notación O 
Dada una función f, estudiaremos aquellas funciones g que a lo sumo crecen tan deprisa como f. 
Al conjunto de tales funciones se le llama cota superior de f y lo denominamos O(f). Conociendo 
la cota superior de un algoritmo se puede asegurar que, en ningún caso, el tiempo empleado será 
de un orden superior al de la cota. 
Cota Inferior. Notación Ω 
Dada una función f, se quieren estudiar aquellas funciones g que a lo sumo crecen tan lentamente 
como f. Al conjunto de tales funciones se le llama cota inferior de f y se denominan Ω(f). 
Conociendo la cota inferior de un algoritmo se puede asegurar que, en ningún caso, el tiempo 
empleado será de un orden inferior al de la cota. 
Orden Exacto. Notación Θ 
Como última cota asintótica, están los conjuntos de funciones que crecen asintóticamente de la 
misma forma. 
Ejemplos 
— f ∈ O( f ) 
— (n+1)2 ∈ O(n 2 ), con c=4, n0=1 
— 3n3 +2n 2 ∈ O(n3 ), con c=5, n0=0 
— P(n) ∈ O(n k ), para todo polinomio P de grado k 
— 3n ∉ O(2n ). Si lo fuese existirían c ∈ ℜ+ , n0 ∈ ℵ tales que ∀ n : n ≥ n0 : 3n ≤ c ⋅ 2n ⇒ ∀ n ≥ 
n0 : (3/2)n ≤ c ⇔ falso pues limn→∞(3/2)n = ∞ 
Ordenes de Complejidad: 
La familia O(f(n)) representa un Orden de Complejidad de donde f(n) es la función más sencilla 
de la familia. 
Las funciones de complejidad algorítmica más habituales en las cuales el único factor del que 
dependen es el tamaño de la muestra de entrada n, ordenadas de mayor a menor eficiencia son: 
Se identifica una Jerarquía de Ordenes de Complejidad en el sentido de que cada orden de 
complejidad inferior tiene a las superiores como subconjuntos. 
• O (1): Complejidad constante. Cuando las instrucciones se ejecutan una vez. 
• O (log n): Complejidad logarítmica. Esta suele aparecer en determinados algoritmos con 
iteración o recursión no estructural, por ejemplo, la búsqueda binaria. 
• O(n): Complejidad lineal. Aparece en la evaluación de bucles simples siempre que la 
complejidad de las instrucciones interiores sea constante. 
• O (n log n): Complejidad cuasi-
lineal. Se encuentra en algoritmos 
de tipo divide y vencerás como por 
ejemplo en el método de 
ordenación quicksort y se 
considera una buena complejidad. 
Si n se duplica, el tiempo de 
ejecución es ligeramente mayor 
del doble. 
• O(n^2): Complejidad 
cuadrática. Aparece en bucles o 
ciclos doblemente anidados. 
Si n se duplica, el tiempo de 
ejecución aumenta cuatro veces. 
• O(n^3): Complejidad 
cúbica. Suele darse en bucles con 
triple anidación. Si n se duplica, el 
tiempo de ejecución se multiplica 
por ocho. Para un valor grande 
de n empieza a crecer 
dramáticamente. 
• O(n^a): Complejidad 
polinómica (a > 3). Si a crece, la 
complejidad del programa es 
bastante mala. 
• O(2^n): Complejidad 
exponencial. No suelen ser muy útiles en la práctica por el elevadísimo tiempo de ejecución. Se 
dan en subprogramas recursivos que contengan dos o más llamadas internas. 
Algoritmos Polinomiales: Aquellos que son proporcionales a n^a. Son en general factibles o 
aplicables, los problemas basados en estos algoritmos son solucionares. 
Algoritmos Exponenciales: En general no son factibles salvo un tamaño de 
entrada n exageradamente pequeño, pero generalmente pertenecen a un universo de problemas de 
los cuales el cómputo se hace imposible. 
Reglas de la Notación Asintótica 
1. Regla de la suma 
Si T1(n) y T2(n) son las funciones que expresan los tiempos de ejecución de dos fragmentos de un 
programa, y se acotan de forma que se tiene: 
y 
Se puede decir que: 
 
2. Regla del producto 
Si T1(n) y T2(n) son las funciones que expresan los tiempos de ejecución de dos fragmentos de un 
programa, y se acotan de forma que se tiene: 
y 
Se puede decir que:Clases de Problemas: 
Clasificación de problemas 
Los problemas matemáticos se pueden dividir en primera instancia en dos grupos: 
Problemas indecidibles: aquellos que no se pueden resolver mediante un algoritmo. 
Problemas decidibles: aquellos que cuentan al menos con un algoritmo para su cómputo. 
Estos problemas se separan en 2: 
Intratables: Aquellos para los que no es factible obtener su solución. 
Tratables: Aquellos para los que existe al menos un algoritmo capaz de resolverlo en un tiempo 
razonable. 
Clases de problemas 
Clase P 
Los algoritmos de complejidad polinómica se dice que son tratables en el sentido de que suelen 
ser abordables en la práctica. Los problemas para los que se conocen algoritmos con esta 
complejidad se dice que forman la clase P. Aquellos problemas para los que la mejor solución que 
se conoce es de complejidad superior a la polinómica, se dice que son problemas intratables. Seria 
muy interesante encontrar alguna solución polinómica (o mejor) que permitiera abordarlos. 
Ejemplos: Todos los algoritmos a los que se les ha podido establecer su tiempo de ejecución. 
Clase NP 
Algunos de estos problemas intratables pueden caracterizarse por el curioso hecho de que puede 
aplicarse un algoritmo polinómico para comprobar si una posible solución es válida o no. Esta 
característica lleva a un método de resolución no determinista consistente en aplicar heurísticos 
para obtener soluciones hipotéticas que se van desestimando (o aceptando) a ritmo polinómico. 
Los problemas de esta clase se denominan NP (la N de no-deterministas y la P de polinómicos). 
Los problemas de la clase P son subconjunto de los de clase NP. 
Ejemplos: Torres de Hanoi, Ordenación por el método Shell 
NP-Completos 
Se conoce una amplia variedad de problemas de tipo NP, de los cuales destacan algunos de ellos 
de extrema complejidad. Gráficamente se puede decir que algunos problemas se encuentran en la 
“frontera externa” de la clase NP. Son problemas NP, y son los peores problemas posibles de clase 
NP. Estos problemas se caracterizan por ser todos “iguales” en el sentido de que si se descubriera 
una solución P para alguno de ellos, esta solución sería fácilmente aplicable a todos ellos. 
Actualmente hay un premio de prestigio equivalente al Nobel reservado para el que descubra 
semejante solución. 
Es más, si se descubriera una solución para los problemas NP-completos, esta sería aplicable a 
todos los problemas NP y, por tanto, la clase NP desaparecería del mundo científico al carecerse 
de problemas de ese tipo. Realmente, tras años de búsqueda exhaustiva de dicha solución, es hecho 
ampliamente aceptado que no debe existir, aunque nadie ha demostrado, todavía, la imposibilidad 
de su existencia. 
 
 
 
 
 
 
 
 
 
Conclusión: 
En un mundo cada vez más dependiente de la tecnología y la automatización, el análisis de 
algoritmos se presenta como un pilar fundamental que influye directamente en nuestra calidad de 
vida, eficiencia y toma de decisiones. A lo largo de este trabajo de investigación, hemos explorado 
las complejidades y los aspectos esenciales de este campo, destacando su importancia en diversas 
aplicaciones y disciplinas. 
Hemos observado cómo el análisis de algoritmos permite no solo entender el rendimiento de estos 
conjuntos de instrucciones, sino también tomar decisiones informadas sobre cuándo y cómo 
implementar algoritmos específicos en función de las necesidades y restricciones de un problema 
dado. La notación "Big O" se ha convertido en una herramienta invaluable para comparar y evaluar 
la eficiencia de los algoritmos, permitiéndonos seleccionar las soluciones más adecuadas para 
abordar desafíos informáticos. 
En resumen, el análisis de algoritmos es un campo en constante evolución que trasciende las 
fronteras de la ciencia de la computación. Su influencia se extiende a la economía, la investigación, 
la salud, la logística y prácticamente todas las esferas de la vida moderna. Como sociedad, es 
esencial que sigamos investigando y mejorando nuestra comprensión de este campo para 
aprovechar al máximo su potencial y garantizar que las soluciones tecnológicas sigan siendo 
eficientes y eficaces. 
A medida que miramos hacia el futuro, podemos estar seguros de que el análisis de algoritmos 
continuará desempeñando un papel central en la optimización de nuestras vidas y sistemas. Su 
estudio y aplicación constante serán cruciales para abordar los desafíos que enfrentamos y para 
impulsar el progreso tecnológico en las décadas venideras. 
 
Bibliografía: 
• http://www.luchonet.com.ar/aed/?page_id=209 
• http://artemisa.unicauca.edu.co/~nediaz/EDDI/cap01.htm 
• https://runestone.academy/ns/books/published/pythoned/AlgorithmAnalysis/QueEsAnalis
isDeAlgoritmos.html 
• https://www.europeanvalley.es/noticias/la-complejidad-de-los-
algoritmos/#:~:text=La%20complejidad%20de%20un%20algoritmo,el%20contexto%20d
e%20los%20algoritmos. 
• https://www2.infor.uva.es/~jvalvarez/docencia/tema5.pdf 
• http://aniei.org.mx/paginas/uam/CursoAA/curso_aa_02.html 
• http://aniei.org.mx/paginas/uam/CursoAA/curso_aa_05.html