Cómo discutir los coeficientes en notación big-O

10

¿Qué notación se usa para discutir los coeficientes de las funciones en notación big-O?

Tengo dos funciones:

  • f(x)=7x2+4x+2
  • g(x)=3x2+5x+4

Obviamente, ambas funciones son , de hecho , pero eso no permite una comparación más allá de eso. ¿Cómo discuto los coeficientes 7 y 3. La reducción del coeficiente a 3 no cambia la complejidad asintótica, pero aún hace una diferencia significativa en el tiempo de ejecución / uso de la memoria.Θ ( x 2 )O(x2)Θ(X2)

¿Es incorrecto decir que es y es ? ¿Hay alguna otra notación que tenga en cuenta los coeficientes? ¿O cuál sería la mejor manera de discutir esto?O ( 7 x 2 ) g O ( 3 x 2 )FO(7 7X2)solO(3X2)

Rafael
fuente
No está mal, es redundante, porque . O(7 7X2)=O(X2)
Vea también nuestra pregunta de referencia .
Raphael

Respuestas:

9

Las notaciones Big- y big- ocultan los coeficientes del término principal, por lo que si tiene dos funciones que son ambas no puede comparar sus valores absolutos sin mirar las funciones mismas. No está mal per se decir que , pero no es informativo porque también es cierto (y, de hecho, es para cualquier constante positiva ).Θ Θ ( n 2 ) 7 x 2 + 4 x + 2 = Θ ( 7 x 2 ) 7 x 2 + 4 x + 2 = Θ ( 3 x 2 ) Θ ( k x 2 ) kOΘΘ(n2)7x2+4x+2=Θ(7x2)7x2+4x+2=Θ(3x2)Θ(kx2)k

Hay otras anotaciones que quizás quieras usar en su lugar. Por ejemplo, la notación es una afirmación mucho más fuerte que big- :ΘΘ

f(x)g(x)limxf(x)g(x)=1

Por ejemplo, , pero la afirmación sería falsa. Puede pensar en la notación tilde como notación que conserva los coeficientes principales, que parece ser lo que está buscando si le importa el coeficiente principal del término de crecimiento dominante.7x2+4x+27x27x2+4x+23x2Θ

templatetypedef
fuente
La notación de Tilde es lo que estoy buscando. Estaba seguro de que había algo que simplemente no podía recordar cómo se llamaba y las búsquedas resultaron infructuosas. ¡Gracias!
6

La tilde es un enfoque. Si quieres seguir con , podrías decirO

F(X)=7 7X2+O(X) y

sol(X)=3X2+O(X) .

Rafael
fuente
Aún mejor: diga f (x) = 7x ^ 2 + o (x ^ 2), usando la notación little-o para aclarar que lo que queda es asintóticamente más pequeño que x ^ 2.
templatetypedef
2
O (x) es estrictamente más pequeño que o (x ^ 2), por lo que usar eso sería menos claro que usar big-O. Por otro lado, usar little-o es definitivamente más común cuando quieres decir que tienes el primer término correcto, porque entonces no necesitas preocuparte por el próximo término. (Y si queremos ser completamente claros, entonces tendríamos que explicar por qué no solo escribimos 7x ^ 2 + 4x + 2 en primer lugar, ya que es exactamente correcto.
Tienes toda la razón ... mis disculpas!
templatetypedef
F(X)=7 7X2+sol(X)sol(X)O(X)F(X)=7 7X2+4 4X+O(1)