El abuso de los grandes-O notación? (versión 2 - simplificado y revisado)

Question

Dada pregunta de examen:

Los algoritmos a Y B tienen la complejidad de las funciones de $f(n)=2 log(n^3)+3n$ y $g(n)=1+0.1n^2$ respectivamente.

Por la clasificación de cada una de las $f$ $g$ $\mathcal{O}(F)$ para un adecuado la función $F$, determinar si a o B es más eficiente cuando se $n$ es de gran tamaño.

No debería la pregunta pedir grande-Theta en lugar de big-O? Considere la siguiente respuesta:

Tenemos $f(n) \in \mathcal{O}(n)$$g(n) \in \mathcal{O}(n^2)$. <--PremiseP

Así que cuando $n$ es grande, $f(n) < g(n)$, con lo que Un algoritmo es más eficiente. <--ConclusionP

Pero es malo para dibujar ConclusionP de PremiseP (sólo considerar el contraejemplo $g(n)=1$).

Por otro lado, la siguiente respuesta es lógica, pero no muy responder a la pregunta:

Tenemos $f(n) \in \Theta(n)$$g(n) \in \Theta(n^2)$.

Así que cuando $n$ es grande, $f(n) < g(n)$, con lo que Un algoritmo es más eficiente.

Fue la pregunta ajustado correctamente, o es mi razonamiento correcto?

Gracias!

Answer 1

Tiene usted razón! y felicitaciones por esta pregunta.

Es molesto cuando la gente (incluyendo a muchas personas en posiciones de enseñanza) uso BigOh completamente equivocado, por ejemplo, frases como: Un Algoritmo es mejor que el de $O(n^2)$ que es una tontería y muestra una falta de entendimiento de BigOh, o lo que es una cota superior asintótica medios. Lo peor es que a veces usted se obliga a utilizarla de manera descuidada a sí mismo con el fin de no confundir al hablar con la gente.

Tenga en cuenta que, aunque hablando en términos de $\Theta$ trabaja en este caso, no siempre lo hacen.

Por ejemplo: $f(n) = n^2$$g(n) = 2n^2$, ambos se $\Theta(n^2)$, pero todavía se puede decir que el $A$ es más eficiente.

También deben ser conscientes de la definición de BigOh/$\Theta$ que está siendo utilizado. El Equipo típico de Ciencias de la definición no implica que el valor absoluto, pero la matemática (Landau) definición.

Answer 2

Tal vez la intención de respuesta fue que a lo largo de las líneas de:

$f \in \mathcal O(n)$ pero $g \not \in \mathcal O(n)$, por lo $g$ va a crecer más que $f$ lo suficientemente grandes valores de $n$.

En el que caso de que la pregunta habría sido correcta.