UNIDAD 2 - Paula226/Base_Datos_AvanzadaCuarto GitHub Wiki

Notación Asintótica

📌 Definición

La notación asintótica es una forma de describir el comportamiento del tiempo de ejecución o uso de memoria de un algoritmo a medida que el tamaño de la entrada crece indefinidamente.

  • Analiza el comportamiento de las funciones en el límite, es decir, su tasa de crecimiento.
  • Se representa como una función cuyo dominio son los números naturales ().
  • Captura el crecimiento del algoritmo para valores grandes de entrada (n).

¿Para qué sirve?

  • Permite comparar algoritmos independientemente del hardware.
  • Se enfoca en la eficiencia a gran escala y no en factores como la implementación, el lenguaje o el compilador.

Factores que pueden influir (aunque no se consideran en la notación asintótica)

  • La velocidad de la computadora.
  • El lenguaje de programación y el compilador.
  • Otros factores de implementación.

Ejemplo

Un algoritmo realiza: 2n² + 3n + 5 operaciones.
Su notación asintótica es: O(n²)
🔍 Porque a medida que n crece, el término cuadrático () domina el comportamiento.


Notación O (Big O)

📌 Definición

  • Describe el límite superior del tiempo de ejecución de un algoritmo.
  • Representa el peor caso posible.
  • Se usa para determinar la eficiencia máxima requerida.

📈 Tipos de orden:

Tipo de Orden Notación
Constante O(1)
Logarítmico O(log n)
Lineal O(n)
Cuadrático O(n²)
Exponencial O(aⁿ), a>2
Factorial O(n!)

📌 ¿Para qué sirve?

  • Asegura que un algoritmo no se comportará peor que cierto límite de tiempo.

Ejemplo

Una búsqueda lineal recorre todos los elementos de una lista:
➡️ O(n)


Notación Ω (Omega)

📌 Definición

  • Representa el límite inferior del tiempo de ejecución.
  • Indica el mejor caso posible.
  • Se dice que un algoritmo es Ω(f(n)) si no puede ejecutarse más rápido que f(n) para entradas suficientemente grandes.

✅ Definición formal

Un algoritmo es Ω(f(n)) si existen constantes positivas c y n₀ tales que para todo n ≥ n₀ se cumple:

T(n) ≥ c · f(n)

Donde:

  • T(n) es el tiempo de ejecución.
  • c es una constante positiva.
  • n₀ es el tamaño mínimo de entrada.

📌 ¿Para qué sirve?

  • Permite saber qué tan eficiente puede llegar a ser un algoritmo.
  • Útil para establecer límites mínimos de eficiencia.

Ejemplo

En búsqueda lineal, si el valor está al inicio de la lista:
➡️ Ω(1) (una sola comparación)


🟰 Notación Θ (Theta)

📌 Definición

  • Representa el caso promedio o comportamiento exacto.
  • Combina el límite superior (O) y el inferior (Ω).
  • Se dice que un algoritmo tiene Θ(f(n)) si su crecimiento es igual a f(n).

Notación formal

Θ(f(n)) = O(f(n)) ∩ Ω(f(n))

¿Para qué sirve?

  • Describe el comportamiento más representativo del algoritmo.
  • Es útil cuando el algoritmo siempre se comporta igual sin importar la entrada.

Ejemplo

Un algoritmo que siempre realiza n operaciones:
➡️ Θ(n)


⚙️ Notación Asintótica Condicional

📌 Definición

  • Analiza la complejidad bajo ciertas condiciones específicas del problema o entrada.
  • Aplica cuando la eficiencia del algoritmo depende de la naturaleza de los datos.

📌 ¿Para qué sirve?

  • Permite analizar algoritmos que se comportan distinto según la entrada.

Ejemplo

En el algoritmo de Quicksort:

  • Mejor caso (el pivote divide en partes iguales): O(n log n)
  • Peor caso (lista ya ordenada): O(n²)

➡️ La complejidad depende condicionalmente de la entrada.


Conclusión: La notación asintótica es fundamental para entender y comparar algoritmos, especialmente cuando se enfrentan a grandes volúmenes de datos. Proporciona una visión clara de su eficiencia en términos teóricos, más allá de las condiciones prácticas de implementación.