Supongamos que tengo una lista de funciones, por ejemplo
¿Cómo los ordeno asintóticamente, es decir, después de la relación definida por
,
suponiendo que sean comparables por pares (ver también aquí )? Usar la definición de parece incómodo, y a menudo es difícil demostrar la existencia de constantes adecuadas y .c n 0
Se trata de medidas de complejidad, por lo que nos interesa el comportamiento asintótico como , y suponemos que todas las funciones toman solo valores no negativos ( ).∀ n , f ( n ) ≥ 0
Respuestas:
Si desea una prueba rigurosa, el siguiente lema a menudo es útil resp. más útil que las definiciones.
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:
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
con ysol∗∈ Ω ( 1 )
luego
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²!
Cuando aparezcan los factoriales, use la fórmula de Stirling :
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 :
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í .
fuente
Limit[f[n]/g[n], n -> Infinity]
y realizar una distinción de casos.Otro consejo: a veces aplicar una función monótona (como log o exp) a las funciones aclara las cosas.
fuente
Skiena proporciona una lista ordenada de las relaciones de dominio entre las funciones más comunes en su libro, The Algorithm Design Manual:
Aquí denota la función inversa de Ackermann .α(n)
fuente
Consejo: dibuje gráficos de estas funciones usando algo como Wolfram Alpha para tener una idea de cómo crecen. Tenga en cuenta que esto no es muy preciso, pero si lo intenta con números suficientemente grandes, debería ver los patrones comparativos de crecimiento. Por supuesto, esto no sustituye a una prueba.
Por ejemplo, pruebe: plot log (log (n)) de 1 a 10000 para ver un gráfico individual o plot log (log (n)) y plot log (n) de 1 a 10000 para ver una comparación.
fuente
Sugiero proceder de acuerdo con las definiciones de varias notaciones. Comience con un par de expresiones arbitrarias y determine el orden de esas, como se describe a continuación. Luego, para cada elemento adicional, encuentre su posición en la lista ordenada utilizando la búsqueda binaria y comparando como se muestra a continuación. Entonces, por ejemplo, clasifiquemos y , las dos primeras funciones de n, para comenzar la lista. 2 nnloglogn 2n
Utilizamos la propiedad de que para reescribir la primera expresión como n log log n = ( 2 log n ) log log n = 2 log n log log nn=2logn nloglogn=(2logn)loglogn=2lognloglogn nloglogn=2lognloglogn∈o(2n) c>0 n0 n≥n0 c(nloglogn)=c(2lognloglogn)<2n
Etc.
fuente
fuente