SEMANA_04_B1 - meruiz22/Analisis-de-Algoritmos GitHub Wiki

Notación asintótica

La notación asintótica es una herramienta matemática utilizada en el análisis de algoritmos para describir el comportamiento de las funciones cuando el tamaño de la entrada n tiende a infinito. Permite comparar la eficiencia de diferentes algoritmos al enfocarse en su tasa de crecimiento, ignorando constantes y detalles específicos como el hardware o el lenguaje de programación.

Notación para el "orden de" (Big O)

La notación Big O es la más comúnmente utilizada para describir el peor caso de un algoritmo, indicando el máximo tiempo o espacio que puede requerir para una entrada de tamaño n.

Definición

Formalmente, una función f(n) es O(g(n)) si existen constantes positivas c y n₀ tales que:

  • 0 ≤ f(n) ≤ c · g(n), ∀ n ≥ n₀

Esto significa que f(n) crece como máximo tan rápido como g(n) para valores grandes de n.
Por ejemplo, si un algoritmo tiene un tiempo de ejecución f(n) = 3n² + 2n + 1000, se simplifica a O(n²), ya que el término n² domina.

Ejemplos

  • Búsqueda lineal: Revisa cada elemento de una lista hasta encontrar el objetivo o terminar. En el peor caso, requiere n comparaciones → O(n).
  • Búsqueda binaria: Divide una lista ordenada por la mitad en cada paso, reduciendo el espacio de búsqueda logarítmicamente → O(log n).
  • Ordenamiento por burbuja: Compara y cambia pares de elementos, realizando hasta n(n-1)/2 comparaciones en el peor caso → O(n²).

Tabla de complejidades comunes

Notación Nombre Ejemplo de Algoritmo Descripción
O(1) Constante Acceso a un elemento por índice Tiempo fijo, independientemente de n.
O(log n) Logarítmica Búsqueda binaria Crece lentamente, dividiendo el problema.
O(n) Lineal Búsqueda lineal Proporcional al tamaño de la entrada.
O(n log n) Lineal-logarítmica Ordenamiento por mezcla (MergeSort) Eficiente para ordenamiento.
O(n²) Cuadrática Ordenamiento por burbuja Cuadrado del tamaño de la entrada.
O(2ⁿ) Exponencial Generar subconjuntos Crece muy rápido, para problemas combinatorios.
O(n!) Factorial Generar permutaciones Extremadamente lento, para problemas exhaustivos.

Referencias