Grandes Oh notación de $7x^2$, confundido

Question

Voy a averiguar el Big-Oh notación de $7x^2$. Echa un vistazo a esto.

Ahora este dice:

Mostrar que $7x^2$ $O(x^3)$ Al $x>7, 7x^2<x^3$,
Así que vamos a $C=1$$k=7$, vemos a $7x^2$$O(x^3)$. Alternativamente, cuando la $x>1, 7x^2<7x^3$, por lo que el $C=7$ y
$k=1$, tenemos la relación de $7x^2$ $O(x^3)$

Por esta lógica no debería el Grande Oh de $7x^2$ ser: $$7x^2<8x^2$$ $$7x^2 \in O(x^2)$$ con C=8 y k=1? Desde $7x^2$ es, obviamente, menos de $8x^2$ por cada $k>=1$. ¿Por qué necesitamos a $x^3$?

Al mismo tiempo, el enlace dice

Deje $f(x)=a_nx^n+…+a_1x+a_0$, donde a0, a1, ..., an-1, an son todos los números reales, entonces f(x) es $O(x^n)$

Y no la mencionada regla específicamente del estado que para un polinomio de grado n, la gran oh va a ser $O(x^n)$?

Lo que me estoy perdiendo aquí?

Answer 1

Como los comentarios ya digo, tienes razón en decir que $7x^2$$O(x^2)$. Pero también es $O(x^3)$ o $O(x^n)$$n \geq 2$. Informalmente, el big-Oh notación da un límite superior de lo rápido que la función crece. Por eso, $7x^2$ crece como una función cuadrática (lo $O(x^2)$), pero también crece más lento que un cúbicos de función (lo $O(x^3)$).

Sin embargo, esta definición genérica, pero no muy útil en general. Si, por ejemplo, decir que el$7x^2$$O(x^5)$$7x^4$$O(x^5)$, no te da ninguna idea acerca de cómo $7x^2$ compara a $7x^4$. El $O(x^5)$ da una muy floja límite superior para el crecimiento asintótico de estas funciones. En otros cursos, usted aprenderá sobre el uso de big-Oh notación. Te da una idea acerca de cómo un algoritmo es eficiente. Es por eso que usted necesita para dar el gran-Oh complejidad como cierre a la menor cota superior como usted puede. Así, se dice casi siempre $7x^2$$O(x^2)$, incluso si, según la definición estricta, también es $O(x^3)$.

Answer 2

Esta notación tiene siempre que me confunde antes, porque los profesores de informática siempre parecen enseñar el concepto de forma incorrecta. Sin duda, los libros de texto enseñan mal.

Si una función $f(x)$ satisface la siguiente igualdad:

$f(x) = O(x^2)$

A continuación, el siguiente también debe ser cierto:

$f(x) = O(x^3)$

Si el estado estacionario de crecimiento de $f(x)$ está delimitado por $x^2$, entonces es también limitada por $x^3$. ¿Por qué es esto? Porque, como vemos en mayores valores de $x$, el polinomio $Ax^3$ podría llegar a superar a $Bx^2$ $A$, $B$ $\in \mathbb{R^+}$.