Si desea una prueba rigurosa, el siguiente lema a menudo es útil resp. más útil que las definiciones.
c=limn→∞f(n)g(n)
- c=0 ⟺f∈o(g) ,
- c∈(0,∞)⟺f∈Θ(g) y
- c=∞ ⟺f∈ω(g) .
Con esto, debería poder ordenar la mayoría de las funciones que aparecen en el análisis de algoritmos¹. Como ejercicio, ¡pruébalo!
Por supuesto, debe poder calcular los límites en consecuencia. Algunos trucos útiles para descomponer funciones complicadas en básicas son:
- Exprese ambas funciones como y compare los exponentes; si su relación tiende a o , también lo hace el cociente original. 0 ∞e…0∞
En términos más generales: si tiene una función convexa, continuamente diferenciable y estrictamente creciente para que pueda volver a escribir su cocienteh
F( n )sol( n )= h ( f∗( n ) )h ( g∗( n ) ) ,
con ysol∗∈ Ω ( 1 )
limn → ∞F∗( n )sol∗( n )= ∞ ,
luego
limn → ∞F( n )sol( n )= ∞ .
Vea aquí una prueba rigurosa de esta regla (en alemán).
Considere la continuación de sus funciones sobre los reales. Ahora puede usar la regla de L'Hôpital ; ¡ten en cuenta sus condiciones²!
- Eche un vistazo al equivalente discreto, Stolz – Cesàro .
Cuando aparezcan los factoriales, use la fórmula de Stirling :
n ! ∼ 2 πnorte---√( nmi)norte
También es útil mantener un conjunto de relaciones básicas que demuestre una vez y use con frecuencia, como:
los logaritmos crecen más lentamente que los polinomios, es decir
α , β > 0( registron )α∈ o ( nβ) para todos .α , β> 0
orden de polinomios:
α<βnorteα∈ o ( nβ) para todos .α < β
Los polinomios crecen más lentamente que los exponenciales:
αc>1norteα∈ o ( cnorte) para todos y .αc > 1
Puede suceder que el lema anterior no sea aplicable porque el límite no existe (por ejemplo, cuando las funciones oscilan). En este caso, considere la siguiente caracterización de las clases de Landau usando limas superior / inferior :
Con tenemosdos: = lim supn → ∞F( n )sol( n )
- 0 ≤ cs< ∞⟺F∈ O ( g) y
- dos= 0⟺F∈ o ( g) .
Con tenemosdoyo: = lim infn → ∞F( n )sol( n )
- 0 < cyo≤ ∞⟺F∈ Ω ( g) y
- ci=∞⟺f∈ω(g) .
Además,
- 0<ci,cs<∞⟺f∈Θ(g)⟺g∈Θ(f) y
- ci=cs=1⟺f∼g .
Comprueba aquí y aquí si mi notación te confunde.
Bene Nota bene: Mi colega escribió una función de Mathematica que hace esto con éxito para muchas funciones, por lo que el lema realmente reduce la tarea a la computación mecánica.
² Ver también aquí .