Funciones de clasificación por crecimiento asintótico

35

Supongamos que tengo una lista de funciones, por ejemplo

nloglog(n),2n,n!,n3,nlnn,

¿Cómo los ordeno asintóticamente, es decir, después de la relación definida por

fOgfO(g) ,

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 0Ocn0

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 ) 0n+n,f(n)0

ENE
fuente
44
Como el OP nunca regresó, estoy eliminando las cosas localizadas y hago una pregunta de referencia a partir de esto.
Rafael

Respuestas:

48

Si desea una prueba rigurosa, el siguiente lema a menudo es útil resp. más útil que las definiciones.

c=limnf(n)g(n)

  • c=0 fo(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 e0
  • 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)g(n)=h(f(n))h(g(n)) ,

    con ygΩ(1)

    limnf(n)g(n)= ,

    luego

    limnf(n)g(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πn(ne)n

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(logn)αo(nβ) para todos .α,β>0

  • orden de polinomios:

    α<βnαo(nβ) para todos .α<β

  • Los polinomios crecen más lentamente que los exponenciales:

    αc>1nαo(cn) 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 tenemoscs:=lim supnf(n)g(n)

  • 0cs<fO(g) y
  • cs=0fo(g) .

Con tenemosci:=lim infnf(n)g(n)

  • 0<cifΩ(g) y
  • ci=fω(g) .

Además,

  • 0<ci,cs<fΘ(g)gΘ(f) y
  • ci=cs=1fg .

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í .

Rafael
fuente
@Juho No públicamente, afaik, pero es elemental escribir usted mismo; calcular Limit[f[n]/g[n], n -> Infinity]y realizar una distinción de casos.
Raphael
20

Otro consejo: a veces aplicar una función monótona (como log o exp) a las funciones aclara las cosas.

Suresh
fuente
55
Esto debe hacerse con cuidado: , pero . 2 2 nO ( 2 n )2nO(n)22nO(2n)
Shaull
2
Secundado La cosa de "aplicar función monótona" parece ser algún tipo de folklore que no funciona en general. Hemos estado trabajando con criterios suficientes y se me ocurrió lo que publiqué en la última revisión de mi respuesta .
Rafael
17

Skiena proporciona una lista ordenada de las relaciones de dominio entre las funciones más comunes en su libro, The Algorithm Design Manual:

n!cnn3n2n1+ϵnlgnnn1/2
lg2nlgnlgnlglgnlglgnα(n)1

Aquí denota la función inversa de Ackermann .α(n)

Robert S. Barnes
fuente
Esa es una lista extrañamente específica. Muchas de las relaciones (lo que sea que signifique exactamente) pueden resumirse en un puñado de lemmata más generales.
Rafael
Es su notación para una relación de dominio.
Robert S. Barnes
11

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.

Dave Clarke
fuente
99
¿Deberíamos realmente recomendar vudú ?
Raphael
+1 por sugerir dibujar gráficos de las funciones, aunque los gráficos vinculados son bastante confusos a menos que sepa lo que significan.
Tsuyoshi Ito
1
Tome una gráfica como pista de lo que le gustaría probar. Esa pista puede estar equivocada, por supuesto.
gnasher729
8

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 nnloglogn2n

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=2lognnloglogn=(2logn)loglogn=2lognloglognnloglogn=2lognloglogno(2n)c>0n0nn0c(nloglogn)=c(2lognloglogn)<2n

3n2n3n=(2log3)n=2nlog32no(3n)=o(2nlog3)

Etc.

Patrick87
fuente
2

NameRunning TimeConstant timeO(1)Inverse Ackermann timeO(a(n))Iterated logarithmic timeO(logn)Log-logarithmicO(nlogn)Logarithmic timeO(logn)Polylogarithmic timepoly(logn)Fractional powerO(nc),where 0<c<1Linear timeO(n)"n log star n" timeO(nlogn)Quasilinear timeO(nlogn)Quadratic timeO(n2)Cubic timeO(n3)Polynomial timepoly(n)=2O(logn)Quasi-polynomial time2O(poly(logn))Sub-exponential time (first definition)O(2nϵ),ϵ>0Sub-exponential time (second definition)2o(n)Exponential time(with linear exponent)2O(n)Exponential time2poly(n)Factorial timeO(n!)

poly(x)=xO(1)

kelalaka
fuente
1
2nlogno(n!)
1
Puse esto para que el nombre de las clases de complejidad se pueda hablar directamente aquí. Sí, Landau trata más sobre un tipo específico de algoritmo en Criptografía.
kelalaka
1
Me opongo a algunas de las opiniones de @ Raphael. He sido matemático e instructor durante muchos años. Creo que, además de probar esas cosas, una mesa grande como esta aumenta la intuición de las personas de manera fácil y enorme. Y los nombres de las clases asintóticas ayudan a las personas a recordar y comunicarse mucho.
Apass.Jack
1
@ Apass.Jack En mi experiencia docente, cuando se les da una mesa, muchos estudiantes la aprenderán de memoria y no ordenarán ninguna función que no esté en la mesa. Tenga en cuenta cómo ese efecto parece explicar muchas de las preguntas sobre el crecimiento asintótico que aterrizan en este sitio. Dicho esto, por supuesto, usaremos lemmata implícito en la tabla si facilita las pruebas, pero eso viene después de aprender a probar la tabla. (Para enfatizar ese punto, las personas que vienen aquí no necesitan ayuda para leer cosas de una mesa. Necesitan ayuda para probar las relaciones).
Raphael
1
@kelalaka "Sí, Landau trata más sobre un tipo específico de algoritmo en Criptografía". - Eso ni siquiera tiene sentido. La notación de Landau es una abreviatura para describir propiedades de funciones matemáticas. No tiene nada que ver con algoritmos y mucho menos con la criptografía, per se.
Raphael