El análisis de la complejidad temporal de un algoritmo es una medida de la cantidad de tiempo que toma ejecutar un algoritmo en función del tamaño de la entrada. Este análisis es crucial para entender la eficiencia de un algoritmo y compararlo con otros.

1. Tiempo de Ejecución: La cantidad de tiempo que un algoritmo tarda en completarse.
2. Tamaño de la Entrada (n): La cantidad de datos que el algoritmo debe procesar.
3. Función de Complejidad Temporal: Una función que describe cómo el tiempo de ejecución de un algoritmo crece con el tamaño de la entrada.

La notación asintótica se utiliza para describir la complejidad temporal de un algoritmo de manera abstracta y simplificada. Las tres notaciones más comunes son:

1. O(n) - Notación Big O: Describe el peor caso.
2. Ω(n) - Notación Omega: Describe el mejor caso.
3. Θ(n) - Notación Theta: Describe el caso promedio.

• O(1): Tiempo constante.
• O(log n): Tiempo logarítmico.
• O(n): Tiempo lineal.
• O(n log n): Tiempo linealítmico.
• O(n^2): Tiempo cuadrático.

1. Identificar las operaciones básicas: Determinar las operaciones que más contribuyen al tiempo de ejecución.
2. Contar las operaciones básicas: Contar cuántas veces se ejecutan las operaciones básicas en función del tamaño de la entrada.
3. Expresar el tiempo de ejecución: Usar la notación asintótica para expresar el tiempo de ejecución.

Consideremos el siguiente algoritmo de búsqueda lineal:

Análisis Paso a Paso

1. Operación Básica: La comparación arr[i] == x.
2. Contar Operaciones: En el peor caso, la comparación se realiza n veces, donde n es el tamaño del arreglo arr.
3. Expresar el Tiempo de Ejecución: En el peor caso, el tiempo de ejecución es O(n).

A continuación, se presenta una tabla comparativa de la complejidad temporal de algunos algoritmos comunes:

Analiza la complejidad temporal del siguiente algoritmo:

Solución

1. Operación Básica: La operación suma += i.
2. Contar Operaciones: El bucle for se ejecuta n veces. La operación suma += i se ejecuta n/2 veces en promedio.
3. Expresar el Tiempo de Ejecución: En el peor caso, el tiempo de ejecución es O(n).

Compara la complejidad temporal de los siguientes dos algoritmos para encontrar el máximo en un arreglo:

Algoritmo A:

Algoritmo B:

Solución

• Algoritmo A:

  • Operación Básica: La comparación arr[i] > maximo.
  • Contar Operaciones: El bucle for se ejecuta n-1 veces.
  • Tiempo de Ejecución: O(n).

• Algoritmo B:

  • Operación Básica: La ordenación arr.sort().
  • Contar Operaciones: La ordenación tiene una complejidad de O(n log n).
  • Tiempo de Ejecución: O(n log n).

Conclusión: El Algoritmo A es más eficiente que el Algoritmo B para encontrar el máximo en un arreglo.

En esta sección, hemos aprendido a analizar la complejidad temporal de los algoritmos, identificar las operaciones básicas, contar las operaciones y expresar el tiempo de ejecución utilizando la notación asintótica. Este conocimiento es fundamental para diseñar algoritmos eficientes y comparar diferentes enfoques para resolver un problema.

En el siguiente módulo, exploraremos la complejidad espacial y cómo afecta la eficiencia de los algoritmos.