Complejidad computacional

Vista previa del material en texto

Algoritmos Computacionales Grupo C 
M. Cruz Apuntes de prueba de regularización Curso de invierno 2022 
 
Complejidad computacional: notación Big O 
La complejidad computacional es un área de la ciencia 
de la computación que se ocupa de medir el 
rendimiento de los algoritmos. La notación Big O es una 
forma de medir la complejidad computacional de un 
algoritmo. 
Ideas principales para estudiantes de universidad 
Para los estudiantes de universidad, es importante 
comprender las siguientes ideas principales sobre la 
notación Big O: 
• La notación Big O se utiliza para estimar el 
rendimiento de un algoritmo. 
• La notación Big O se basa en el peor de los 
casos. 
• La notación Big O se utiliza para comparar el 
rendimiento de diferentes algoritmos. 
Recomendaciones para estudiantes de universidad 
Para los estudiantes de universidad que están 
aprendiendo sobre la notación Big O, se recomiendan 
las siguientes actividades: 
• Practicar mucho. La mejor manera de aprender 
sobre la notación Big O es practicar con 
frecuencia. 
• Buscar ayuda cuando sea necesario. Si tienes 
problemas para entender un concepto o resolver 
un problema, no dudes en pedir ayuda a un 
profesor o a un tutor. 
• Participar en proyectos. Trabajar en proyectos te 
ayudará a aplicar tus conocimientos sobre la 
notación Big O en el mundo real. 
Explicación 
La notación Big O se utiliza para estimar el rendimiento 
de un algoritmo. La notación Big O se basa en el peor 
de los casos, que es el 
caso en el que el 
algoritmo requiere más 
tiempo para ejecutarse. 
La notación Big O utiliza 
una letra mayúscula O 
para representar el 
orden de magnitud del 
tiempo de ejecución del 
algoritmo. El orden de 
magnitud es el factor 
que multiplica al tamaño 
de la entrada del 
algoritmo para obtener 
una estimación del 
tiempo de ejecución. 
Por ejemplo, un 
algoritmo que tiene un 
tiempo de ejecución de 
O(n) se ejecutará en un 
tiempo proporcional al 
tamaño de la entrada 
del algoritmo. Esto 
significa que si el 
tamaño de la entrada se 
duplica, el tiempo de 
ejecución del algoritmo 
se duplicará. 
Tipos de complejidad 
Hay diferentes tipos de 
complejidad 
computacional, que se 
clasifican según el tipo 
de recurso que se mide. 
Los tipos de 
complejidad más 
comunes son: 
Algoritmos Computacionales Grupo C 
M. Cruz Apuntes de prueba de regularización Curso de invierno 2022 
• Complejidad temporal: mide el tiempo que tarda 
un algoritmo en ejecutarse. 
• Complejidad espacial: mide la cantidad de 
memoria que utiliza un algoritmo. 
• Complejidad de comunicación: mide la cantidad 
de datos que un algoritmo intercambia con otros 
procesos. 
Notación Big O para la complejidad temporal 
La notación Big O para la complejidad temporal se 
utiliza para estimar el tiempo de ejecución de un 
algoritmo. Los tipos de complejidad temporal más 
comunes son: 
• O(1): El algoritmo se ejecuta en un tiempo 
constante, independientemente del tamaño de la 
entrada. 
• O(log n): El algoritmo se ejecuta en un tiempo 
proporcional al logaritmo del tamaño de la 
entrada. 
• O(n): El algoritmo se ejecuta en un tiempo 
proporcional al tamaño de la entrada. 
• O(n log n): El algoritmo se ejecuta en un tiempo 
proporcional al producto del tamaño de la 
entrada y el logaritmo del tamaño de la entrada. 
• O(n^2): El algoritmo se ejecuta en un tiempo 
proporcional al cuadrado del tamaño de la 
entrada. 
Conclusión 
La notación Big O es una herramienta importante para 
la comprensión de la complejidad computacional. Los 
estudiantes de universidad deben comprender la 
notación Big O para poder comparar el rendimiento de 
diferentes algoritmos.