Entender la notación big O

Question

No soy matemático ni mucho menos y estoy tratando de traducir algunos términos matemáticos a términos matemáticos sencillos. Por favor, no te rías, ¡lo considero complicado!

Las ecuaciones en cuestión son

O(n) and O(n ^ 2)

Ahora, he leído sobre Wiki ¡sobre esto pero ha sido escrito (OMI) para gente que ya lo entiende!

Creo que n ^ 2 se traduce en the power of , en este caso también es el equivalente a elevar al cuadrado (es decir n * n ).

Sin embargo, no puedo entender O en términos de lo que está describiendo. La Wiki dice que es el comportamiento limitante. Entonces, ¿esto significa O ¿es más una descripción que una función o un comando? A mi entender, las siguientes 2 ecuaciones son las mismas

O(n^2)

n^2

Answer 1

Rápido, $O(n^2)$ es cualquier función $f=f(n)$ tal que $$\left| \frac{f(n)}{n^2} \right|$$ permanece acotado como $n \to +\infty$ . Puede ser $n^2$ mismo, pero también puede ser $n$ o $\sin \cos n$ etc.

Answer 2

Lo formalmente correcto $O$ -La anotación ha sido explicada en http://www.artofproblemsolving.com/Forum/viewtopic.php?f=296&t=31517&start=20 . Es decir, supongamos que nos han dado un positivo $g$ definida en una vecindad perforada de $x_0$ . Ahora $O_{x_0}(g)$ es la clase de todas las funciones $f$ de manera que la relación $f/g$ está acotado en alguna vecindad puntuada de $x_0$ . Esta definición y notación es más rigurosa que, por ejemplo, la que se da en algunos cursos universitarios de informática.