Big-O La Interpretación

Question

Tengo problemas para entender lo que el "Big O" notación, o notación asintótica. Por ejemplo, si usted tiene $\sin(x)=x+O(x^3)$, ¿qué significa esto? Nadie puede describir de una forma sencilla? He intentado buscarla pero las explicaciones no ayuda mucho.

Gracias.

Answer 1

Nota: por lo general el abuso de la notación y escribir $f(x) = \mathcal{O}(g(x))$ en lugar de $f(x) \in \mathcal{O}(g(x))$. Sin embargo, $g(x) \not = \mathcal{O}(f(x))$ en general, porque las $g(x) \notin \mathcal{O}(f(x))$ en general.

Si $f(x) \in \mathcal{O}(g(x))$, para las grandes $x$, $f(x)$ tiene la misma tasa de crecimiento en $g(x)$ o $f(x)$ tiene una menor tasa de crecimiento de $g(x)$. Cuando escribimos

$$\sin(x) = x + \mathcal{O}(x^3) \text{ as $x \rightarrow 0$}$$

nos referimos a $\sin(x)$ es igual a$x$, además de una cierta cantidad que es "un Gran Oh de $x^3$." La última cantidad no se indica exactamente, pero "Big Oh" nos dice que el valor absoluto de la última cantidad no es más que una constante positiva veces $x^3$. Incluso podemos escribir muchos familiares de los resultados de cálculo como $\sin(x) \leq 1$ $n! \sim {(2\pi)^{1/2}}{n^{1/2}}{n^n}{e^{-n}}$ (a Stirling aproximación) de usar el Big Oh:

$$\sin(x) = \mathcal{O}(1) \text{ as $x \rightarrow 0$}$$ $$n! = \mathcal{O}({n^{1/2}}{n^n}{e^{-n}}) \text{ as $x \rightarrow +\infty$}.$$

Otro familiar resultado

$$\mathop{\lim}\limits_{x \to 0}\frac{{\sin(x)}}{x} = 1$$

puede ser escrita como

$$\sin(x) = \mathcal{O}(x) \text{ as $x \rightarrow 0$}$$

pero ya que el límite es de $1$, podemos escribir $\sin(x) \sim x \text{ as $x \rightarrow 0$}$.

Usted puede pensar en "Big Oh" como $$\mathop{\lim \sup}\limits_{x \to \infty} \left|\frac{{f(x)}}{{g(x)}}\right| = K \in \mathbb{R^+} \Rightarrow f(x) \in \mathcal{O}(g(x)).$$

Técnicamente:

$$\mathop{\lim \sup}\limits_{x \to \infty} \left|\frac{{f(x)}}{{g(x)}}\right| = K \in \mathbb{R^+} \Rightarrow f(x) \in \mathcal{O}(g(x)) \wedge f(x) \in \Theta(g(x)) \wedge f(x) \in \Omega(g(x))$$

donde $\Theta$ $\Omega$ están relacionados con notaciones asintóticas.

Ver Concretas Matemáticas por Graham, Knuth, y Patashnik para una buena introducción a asymptotics.

Answer 2

Una de las principales razones para el uso de big-Oh/asintótica/notación de Landau es entender cómo algunos complicado función obras de ampliación en más fáciles de funciones, tomando el argumento de a $\infty$ (o donde quieras) y mirando en el mayor de los términos de RHS. En tu caso la idea es que como $x \to 0$, $\sin x =O(x)$ por expansión en serie de Maclaurin. Otro ejemplo interesante voy a mostrar aquí es Armónica de la suma:

$$ H(n)=\sum_{k=1}^{n} \frac{1}{k} = O( \log n) $$