¿Puede alguien explicar la definición matemática de BigO?

Question

Estoy aprendiendo sobre la notación Big O para mi clase de Ciencias de la Computación y mi instructor proporcionó la siguiente definición:

Preguntas:

1) ¿Qué significa para $f(n) = \mathcal{O}(g(n))$ ? Entiendo cómo funcionan las funciones matemáticas pero esto no tiene sentido para mí porque nunca dice qué funciones f o g representan. Sé que n representa el conjunto de datos pero eso es todo.

2) Dice $C$ y $n_0$ son constantes positivas. Entiendo $C$ que representa una constante, pero ¿por qué menciona $n_0$ ¿es una constante? ¿Esto es básicamente decir que todos los valores del conjunto de datos tienen que ser números positivos?

3) ¿Cómo es que en el ejemplo hay una flecha que apunta a $n^2$ que dice $c = 1$ ?

Gracias por la ayuda chicos. Soy un gran codificador, pero no un tipo de matemáticas. ¡Esto es muy frustrante y aprecio la ayuda!

Answer 1

La convención es escribir $f(n) = O(g(n))$ como una ecuación, pero la igualdad no es realmente lo que se está discutiendo. En cambio, las notaciones big-O representan cada una una clase de funciones, y realmente significa $f(n) \in O(g(n))$ o que $f(n)$ es una función que está en la misma clase de big-O que $g(n)$ .

El $n_0$ sólo está ahí como una forma de decir "cuando $n$ es lo suficientemente grande, la desigualdad se mantiene para alguna constante $c$ para todos los siguientes $n$ como $n$ crece hasta el infinito".

"c = 1" está ahí porque " $\dfrac{n^2}2 - \dfrac{n}2 \le n^2$ " es equivalente a " $\dfrac{n^2}2 - \dfrac{n}2 \le 1 \cdot n^2$ ", que equivale a " $\dfrac{n^2}2 - \dfrac{n}2 \le cn^2$ donde $c = 1$ "

Answer 2

Como parece que no quieres una definición formal, te daré el significado de la notación "O grande".

En informática, se utiliza esta notación cuando se trata de la complejidad de los algoritmos, es decir, el número de "operaciones elementales" que realiza el programa. Te da una estimación del tiempo que tarda tu código en darte la salida.

$n$ aquí representa la "longitud" de su entrada, y $f(n)$ es una función que indica la complejidad de su algoritmo.

Por ejemplo, un algoritmo simple con entrada $n$ y la salida $n^2$ como nosotros

a=0;
for (i=0;i<n;i++)
    a=a+n;

tiene una complejidad de $\;f(n)=n$ mientras que

a=n*n;

tiene una complejidad de $\;g(n)=1$ .

Así que las funciones utilizadas $f(n), g(n)$ y el parámetro $n$ son siempre positivos.

Normalmente, cuando $n$ (la entrada) es pequeña, podemos controlar manualmente cómo funciona el algoritmo, y cuál es su complejidad $f(n)$ es, pero cuando $n$ es grande, perdemos este control, y tenemos que estudiar $f(n)$ de forma asimétrica, es decir, buscamos funciones que se aproximen a $f(n)$ . Así que nos ponemos en el caso de que $n$ es grande, y lo formalizamos diciendo que $n\ge n_0$ , donde $n_0$ es una gran constante.

Diciendo que $f(n)=O(g(n))$ significa que existe una constante $c\ge 0$ para lo cual $\;f(n)\le cg(n)\;$ para todos $n$ mayor que un determinado $n_0$ .

Recuerda que $f(x)$ es la complejidad de un algoritmo. Significa que si tienes otro algoritmo que se ejecuta en $cg(n)$ La primera es mejor.

Por ejemplo, en el caso anterior, tenemos $f(n)=n$ y $g(n)=1$ , por lo que se puede decir que $\;g(n)=O(f(n))\;$ porque, si pones $c=1$ , $n_0=1$ es cierto que $\;g(n)=1\le cf(n)=n\;$ para todos $n\ge n_0=1$

En su figura tiene otro ejemplo: suponga que tiene un algoritmo con complejidad $f(n)=n^2/2-n/2$ . Desde $\;f(n)\le n^2$ para todos $n$ esto significa que si se tiene otro algoritmo con complejidad $n^2$ la primera es mejor, y se puede escribir $\;f(n)=O(n^2)$