Complejidad Algorítmica

Complejidad Algorítmica

• La complejidad algorítmica mide los recursos de tiempo (complejidad temporal) y espacio (complejidad espacial) que requiere un algoritmo para un tamaño de entrada arbitrario.
• La complejidad temporal es la cantidad de tiempo que tarda un algoritmo en ejecutarse en función de la longitud de la entrada.
• La complejidad espacial es la cantidad de espacio de memoria que ocupa un algoritmo en función de la longitud de la entrada.
• Se centra en cómo crecen los recursos a medida que aumenta el tamaño de la entrada.

Importancia

• Ayuda a comprender y predecir el rendimiento del algoritmo.
• Es importante para determinar si un algoritmo será adecuado para grandes entradas.
• Guía en la elección de algoritmos y estructuras de datos eficientes.

Expresión de la Complejidad

• Se utiliza la notación Big O para expresar la complejidad de un algoritmo.
• Proporciona un límite superior del peor de los casos.
• Se centra en el término dominante (el que crece más rápido).

Clases de Complejidad Comunes

• O(1) (Constante): El tiempo de ejecución es constante, independientemente del tamaño de la entrada. Ejemplo: Acceder a un elemento en una matriz por índice.
• O(log n) (Logarítmica): Generalmente implica algoritmos que dividen el tamaño del problema en cada paso. Ejemplo: Búsqueda binaria.
• O(n) (Lineal): El tiempo de ejecución aumenta linealmente con el tamaño de la entrada. Ejemplo: Búsqueda simple, recorrer una matriz.
• O(n log n) (Log-lineal): Se encuentra a menudo en algoritmos de clasificación eficientes. Ejemplos: Ordenamiento por mezcla, quicksort (caso promedio).
• O(n^2) (Cuadrática): El tiempo de ejecución aumenta con el cuadrado del tamaño de la entrada. Ejemplos: Ordenamiento de burbuja, ordenamiento por selección.
• O(n^3) (Cúbica): Común en operaciones de matriz o algoritmos con tres bucles anidados. Ejemplo: Multiplicación de matrices.
• O(2^n) (Exponencial): El tiempo de ejecución se duplica con cada adición al conjunto de datos de entrada. Ejemplo: Encontrar todos los subconjuntos de un conjunto.
• O(n!) (Factorial): El tiempo de ejecución crece factorialmente con el tamaño de la entrada. Ejemplo: Problema del viajante (enfoque de fuerza bruta).
• O(n^n) (n a la n): Extremadamente lento.
• O(1/n) (Inversa): Cuanto mayor es el tamaño de la entrada, más rápido se completa.
• O(√n) (Raíz n): Se utiliza principalmente en algoritmos de búsqueda y teoría de números.
• O(log log n) (Logaritmo doble): Raramente surge al analizar algoritmos. Ejemplo: Búsqueda por interpolación.
• O(n^c) (Polinómica): Donde c es una constante. Incluye lineal, cuadrática, cúbica, etc.
• O(c^n) (Exponencial): Donde c es una constante mayor que 1.
• O(e^n) (e a la potencia de n): Crece más rápido que exponencial.

Determinación de la Complejidad

• Identificación de Operaciones: Determinar las operaciones básicas que realiza el algoritmo.
• Conteo de Operaciones: Contar cuántas veces se ejecuta cada operación en función del tamaño de la entrada.
• Término Dominante: Identificar el término que crece más rápido a medida que aumenta el tamaño de la entrada.
• Expresión en Big O: Escribir la complejidad utilizando la notación Big O, eliminando constantes y términos no dominantes.

Consejos

• Los bucles anidados a menudo indican una complejidad de O(n^2) o O(n^3).
• Los algoritmos de dividir y conquistar a menudo tienen una complejidad de O(log n) u O(n log n).
• Se debe ser consciente de los escenarios del peor caso, el caso promedio y el mejor caso.

Conclusión

• Comprender la complejidad algorítmica es crucial para diseñar algoritmos eficientes y escalables.