Universidad Mariano Gálvez de Guatemala
Sede universitaria: Amatitlán
Carrera: Ingeniería en Sistemas y Ciencias de la Computación
Curso: PROGRAMACIÓN III
Sección: “ A “
Catedrático: Ing. Joaquin Milian
COMPLEJIDAD ALGORTIMICA
Nombre: Kaisy Lauren Garcia Díaz
Carnet: 6590-21-19058
Fecha: 01 de mayo del 2024
KAISY L. GARCIA D.
COMPLEJIDAD ALGORITMICA:
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
algoritmos. Esto se debe a que muchos problemas matemáticos se pueden
resolver utilizando 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. Una de las más
comunes es contar el número de operaciones básicas (como suma o
multiplicación) que realiza el algoritmo. Esto se conoce como 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 complejidad espacial del
algoritmo.
Las complejidades temporales y espaciales de un algoritmo se pueden expresar
utilizando 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 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.
Al evaluar la complejidad de un algoritmo, simplemente no tiene sentido
considerar estos factores; en cualquier caso, están fuera de nuestro control. La
notación Big O expresa la complejidad del algoritmo en sí, no el "entorno"
en el que se ejecuta.
La complejidad algorítmica es un concepto fundamental en programación que se
refiere a la cantidad de recursos computacionales que un algoritmo necesita para
resolver un problema en función del tamaño de la entrada. Se suele medir en
términos de tiempo de ejecución (complejidad temporal) y espacio en memoria
(complejidad espacial).
KAISY L. GARCIA D.
La notación Big O:
En las afirmaciones anteriores, vimos que para un arreglo de tamaño n, la
búsqueda lineal realizara n operaciones para completar la búsqueda. Por otro
lado, la búsqueda binaria realiza un número log(n) de operaciones (ambas para
sus peores casos).
Cuando analizamos un algoritmo, utilizamos una notación para representar su
complejidad temporal y esa notación es llamada Big O.
Por ejemplo: la complejidad temporal para la búsqueda lineal puede
representarse como O(n) y O(log n) para la búsqueda binaria
(donde n y log(n) son el número de operaciones).
La complejidad temporal o las notaciones Big O para algunos algoritmos
populares se enumeran a continuación:
1. Búsqueda binaria: O(log n)
2. Búsqueda lineal: O(n)
3. Ordenamiento rápido (Quick Sort): O(n * log n)
4. Ordenamiento por selección: O(n * n)
5. Problema del viajero: O(n!)
En resumen, la notación Big O es una notación matemática que nos sirve para
poner nota a la velocidad de procesamiento de un algoritmo atendiendo a cómo
se comporta conforme aumenta el tamaño del trabajo a procesar, por lo que nos
sirve para clasificar la eficacia de los mismos. Útil tanto para valorar las
necesidades de procesamiento como de espacio necesario para llevar a cabo el
algoritmo, y en definitiva valorar qué tan bueno es un algoritmo dado para
resolver problemas muy grandes, ya que aparentemente puede ser bueno para
unos valores dados, pero fallar según escala el tamaño de entrada:
1. Qué: la notación Big O es una forma de poner nota a la eficiencia de un
algoritmo
2. Cuanto: sólo necesitamos simplificar a si es constante, lineal, logarítmica
o cuadrática
3. Dónde: en el análisis de algoritmos de programación, tanto tiempo como
espacio necesario
4. Cuándo: queremos evaluar y/o comparar la eficacia de un algoritmo,
estructura de datos,...
5. Cómo: comparando la velocidad de crecimiento de una magnitud
(tiempo) respecto la otra (tamaño entrada)
KAISY L. GARCIA D.
6. Por qué: necesitamos valorar la viabilidad de nuestras soluciones en
determinadas situaciones
COMPLEJIDAD TEMPORAL:
La complejidad temporal es el número de operaciones que realiza un algoritmo
para completar su tarea (considerando que cada operación dura el mismo
tiempo). El algoritmo que realiza la tarea en el menor número de operaciones se
considera el más eficiente en términos de complejidad temporal.
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.
KAISY L. GARCIA D.
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:
Jerarquía de complejidad
O(1) ⊂ O(log n) ⊂ O(n) ⊂ O(n log n) ⊂ O(n²) ⊂ O(n³) ⊂ O(2ⁿ) ⊂ O(n!)
KAISY L. GARCIA D.
COMPLEJIDAD ESPACIAL:
1. Complejidad Espacial (O(1)) - Espacio constante:
La complejidad espacial O(1) significa que el espacio utilizado por el
algoritmo es constante, es decir, no depende del tamaño de la entrada. No
importa cuántos elementos procese el algoritmo, siempre utilizará la misma
cantidad de memoria.
2. Complejidad Espacial (O(n)) - Espacio lineal:
La complejidad espacial O(n) indica que el espacio utilizado por el algoritmo
aumenta de manera lineal con el tamaño de la entrada. Por cada elemento
adicional en la entrada, el algoritmo requiere una unidad adicional de espacio.
3. Complejidad Espacial (O(n²)) - Espacio cuadrático:
La complejidad espacial O(n²) significa que el espacio utilizado por el
algoritmo crece cuadráticamente con el tamaño de la entrada. Algoritmos con
bucles anidados suelen tener esta complejidad espacial.
4. Complejidad Espacial (O(log n)) - Espacio logarítmico:
La complejidad espacial O(log n) indica que el espacio utilizado por el
algoritmo aumenta de forma logarítmica con el tamaño de la entrada.
Algoritmos que dividen el problema en partes más pequeñas suelen tener
esta complejidad espacial.
5. Complejidad Espacial Cúbica (O(n³)) - Espacio cúbico:
La complejidad espacial cúbica O(n³) significa que el espacio utilizado por el
algoritmo crece cúbicamente con el tamaño de la entrada. Algoritmos con
bucles anidados que tienen un factor de crecimiento cúbico pueden requerir
una cantidad considerable de memoria para entradas grandes.
6. Complejidad Espacial Polinómica (O(n^k)) - Espacio polinómico:
La complejidad espacial polinómica O(n^k) indica que el espacio utilizado por
el algoritmo crece según una potencia de la entrada. Aquí, 'k' representa el
grado del polinomio. Algoritmos con complejidad espacial polinómica pueden
requerir una cantidad de memoria razonable para entradas moderadas, pero
pueden volverse imprácticos para entradas grandes dependiendo del grado
del polinomio.
KAISY L. GARCIA D.
7. Complejidad Espacial Exponencial (O(2^n)) - Espacio exponencial:
La complejidad espacial exponencial O(2^n) significa que el espacio utilizado
por el algoritmo crece exponencialmente con el tamaño de la entrada.
Algoritmos con esta complejidad pueden requerir una cantidad de memoria
que crece de forma muy rápida y pueden volverse imprácticos incluso para
entradas moderadamente grandes.
KAISY L. GARCIA D.
MAPA MENTAL:
KAISY L. GARCIA D.
