Introducción a la Complejidad Algorítmica

1. Qué es la Complejidad Algorítmica? #

La complejidad algorítmica es el estudio de cómo el rendimiento de un algoritmo cambia en función del tamaño de la entrada. Nos ayuda a entender cuán eficiente es un algoritmo en términos de tiempo y espacio.

Por ejemplo, si tenemos dos formas de resolver un problema, queremos elegir la que sea más rápida y use menos memoria.

✅ Ejemplo de un problema simple:

• Queremos sumar los primeros n números naturales.

Diferentes formas de resolverlo:

1. Usando un bucle (sumamos uno por uno).
2. Usando una fórmula matemática (más eficiente).

Veamos ambos enfoques en varios lenguajes.

Ejemplo 1: Suma con un bucle (O(n)) #

Ejemplo 2: Suma con fórmula matemática (O(1)) #

2. Diferencia entre Complejidad Temporal y Espacial #

Complejidad Temporal #

• Se refiere a cuánto tiempo tarda un algoritmo en ejecutarse en función de la cantidad de datos.
• Se mide en función del tamaño de la entrada n.

Complejidad Espacial #

• Se refiere a cuánta memoria utiliza un algoritmo.
• Un algoritmo que almacena todos los datos en un array consume más memoria que uno que usa solo unas pocas variables.

✅ Ejemplo de espacio usado en memoria

• Este algoritmo usa O(n) de memoria porque almacena todos los números en un array.
• Si solo queremos sumarlos sin almacenarlos, usamos O(1), como en la función de suma sin array.