Semana 3 - Complejidad Algorítmica y Notación Big O

 Complejidad Algorítmica y Notación Big O

Un algoritmo es una secuencia finita y precisa de pasos para resolver un problema. Esta semana aprendimos que no todos los algoritmos son iguales. La complejidad algorítmica es el estudio de cuántos recursos (principalmente tiempo de ejecución y espacio en memoria) consume un algoritmo en función del tamaño de sus datos de entrada, que representamos como "n". El objetivo es poder comparar dos algoritmos de forma objetiva y determinar cuál es más eficiente.

Medir la eficiencia con un cronómetro es inútil, ya que depende de la velocidad del procesador, el lenguaje, etc. Por ello, utilizamos la Notación Big O (Gran O). Esta notación describe cómo se comporta un algoritmo en el peor escenario posible, a medida que el tamaño de la entrada n crece. Nos permite ignorar constantes (ej. 2n vs 5n) y enfocarnos en el orden de crecimiento. Las clases de complejidad clave son:

• O(1) (Constante): El tiempo es el mismo sin importar n. (Ej: Acceder a un índice de un arreglo array[5]).
• O(log n) (Logarítmico): El tiempo aumenta muy lentamente. El algoritmo divide el problema en cada paso. (Ej: Búsqueda binaria).
• O(n) (Lineal): El tiempo es directamente proporcional a n. Si n se duplica, el tiempo se duplica. (Ej: Un solo bucle for que recorre un arreglo).
• O(n²) (Cuadrático): El tiempo aumenta exponencialmente. Si n se duplica, el tiempo se cuadruplica. (Ej: Dos bucles for anidados).
• O(2^n), O(n!) (Exponencial/Factorial): Crecimiento explosivo. Son algoritmos que se vuelven inviables muy rápidamente con n pequeños.

Las diapositivas nos mostraron un ejemplo claro con la búsqueda secuencial:

• Mejor Caso (Omega - Ω): Encontrar el elemento en la primera posición. Complejidad: Ω(1).
• Peor Caso (Big O - O): Encontrar el elemento en la última posición, o no encontrarlo. El bucle se ejecuta n veces. Complejidad: O(n).

 

Conclusión

 Este es, para mí, uno de los temas más cruciales. Escribir código que funciona para n=10 es fácil. Escribir código que escala y sigue funcionando eficientemente para n=1,000,000 es el verdadero desafío de la ingeniería. La notación Big O es el lenguaje profesional que usamos para analizar y predecir el rendimiento. Me permite identificar cuellos de botella en un sistema antes de que falle en producción y justificar por qué una solución aparentemente más compleja (como un algoritmo O(n log n)) es superior a una más simple (O(n²)).