Semana 5 - leosaq/AnalisisDeAlgoritmos GitHub Wiki
Caracterización de los tiempos de ejecución
Esta sección analiza cómo se comporta un algoritmo respecto al tiempo que necesita para ejecutarse, en función del tamaño de su entrada. Se utilizan diferentes notaciones asintóticas para describir distintos escenarios.
Notación Ω (Omega)
La notación Omega (Ω) representa el límite inferior del tiempo de ejecución de un algoritmo, es decir, el mejor caso posible. Nos dice que el algoritmo no puede ejecutarse más rápido que ese límite para entradas grandes.
Ejemplo:
Si un algoritmo tiene una complejidad de Ω(n), quiere decir que en el mejor de los casos realizará como mínimo n operaciones.
Esta notación es útil para entender el rendimiento mínimo garantizado de un algoritmo.
Notación Θ (Theta)
La notación Theta (Θ) indica el comportamiento exacto del algoritmo, es decir, su crecimiento tanto en el mejor como en el peor caso. Se usa cuando el límite superior y el inferior coinciden.
Ejemplo:
Si un algoritmo tiene una complejidad de Θ(n²), significa que en todos los casos su tiempo de ejecución crece proporcionalmente al cuadrado del tamaño de la entrada.
Esta notación es la más precisa para describir el comportamiento general de un algoritmo.
Notación Asintótica Condicional
La notación asintótica condicional se aplica cuando el análisis del algoritmo depende de ciertas condiciones específicas, como características particulares de la entrada.
Ejemplo:
Un algoritmo puede comportarse como Θ(n) si la lista está ordenada, pero como Θ(n log n) si está desordenada.
En este tipo de análisis, el rendimiento varía según supuestos o restricciones sobre la entrada. Por eso, se considera una caracterización más detallada y dependiente del contexto.