Explica la complejidad temporal en el contexto de la programación competitiva de una manera informal.
user
El análisis de la complejidad temporal de un algoritmo es una técnica que permite entender qué tan rápido un algoritmo es sin necesidad de tener que implementarlo ni ejecturar dicho programa.
La idea es la siguiente: bajo los modelos computacionales estándar (por ejemplo, Random Access Machine), se pueden definir ciertas operaciones atómicas, como suma, restar, multiplicar y dividir dos números, también modificar un byte o acceder a una posición en memoria. Entonces, podemos definir la complejidad de un programa de acuerdo a la cantidad de operaciones atómicas realizadas con respecto al tamaño de la entrada.

Cabe mencionar que aunque consideramos todas las operaciones atómicas igual de baratas, en realidad no lo son; por ejemplo, la multiplicación es más cara que la adición. Debido a eso, obviamos las constantes en nuestro análisis, y nos preocupamos más por el crecimiento de la cantidad de operaciones.

Por ejemplo, los siguientes bucles en Python tienen la misma complejidad computacional, aunque uno hace n iteraciones, otro hace 3*n + 2 iteraciones, y el otro hace n/2 iteraciones.

sum = 0
for i in range(n):
     sum += i

for i in range(3*n + 2):
      sum += i

for i in range(n//2):
      sum += i

Las complejidades computacionales más populares son:
- logarítmica: O(log n), es cuando la cantidad de operaciones crece de manera lineal cuando n crece exponencialmente. Un ejemplo es la búsqueda binaria.
- lineal: O(n), cuando la cantidad de operaciones es proporcional a n, por ejemplo, la búsqueda lineal.
- O(n log n), por ejemplo ordenar una lista de n elementos con el algoritmo de merge sort.
- O(n^2), por ejemplo ordenar una lista de n elementos con el algoritmo de bubble sort.
- O(2^n), exponencial, por ejemplo extraer todos los subconjuntos de un conjunto de tamaño n.
assistant