Actualmente estoy realizando un curso de algoritmos y me he encontrado con el siguiente gráfico enter  descripción de la imagen aquí

Me cuesta entender qué significa f (n) , qué significa g (n) y qué c y n0 significa. Además, quiero saber cómo se relacionan con el concepto de límites y qué significa eso.

La mayoría de los tutoriales comienzan explicando cómo se relacionan los términos anteriores, pero no qué significan.

2
Nacho Libre 16 oct. 2020 a las 16:56

1 respuesta

La mejor respuesta

Imagina que escribiste un programa para ordenar una lista. Su programa ingresa una lista, realiza cálculos durante algún tiempo y luego genera una lista ordenada.

La notación "big-O" f(n) = O(g(n)) es una forma de comparar dos funciones f y g.

Cuando se trata de números, está acostumbrado a hacer comparaciones, por un instante "x

Cuando se trata de funciones, tenemos varias formas diferentes de hacer comparaciones. Por ejemplo, podría decir "la función f es siempre más pequeña que la función g" y escribiría eso formalmente: "forall n, f (n)

Sin embargo, esta comparación es un poco extrema. En el gráfico que ha mostrado en su pregunta, la función violeta no siempre es más pequeña que la función azul. Pero puede notar que solo es más grande para unos pocos valores pequeños de n. Entonces tiene sentido decir "después de unos pocos valores iniciales, la función f finalmente se vuelve más pequeña que la función cg" o formalmente "existe un número n0 tal que forall n> n0, f (n)

Ahora, las funciones que queríamos comparar originalmente eran f y g, no f y cg. Sin embargo, tal vez no nos importe una constante multiplicativa; tal vez solo nos importe cómo se comporta f (n) cuando n aumenta, y cómo se comporta g (n) cuando n aumenta. Por ejemplo, tal vez observe que cuando n es 10 veces más grande, f (n) se vuelve aproximadamente 100 veces más grande. Esto significa que f (n) es aproximadamente proporcional an ^ 2. No nos importa si f es aproximadamente igual an ^ 2 + 5 o 7 * n ^ 2 + 2 * n + 12. Lo que nos importa es que es aproximadamente proporcional a n ^ 2.

Entonces, la notación Big-O nos da una manera de comparar dos funciones f (n) y g (n) mientras ignoramos las constantes multiplicativas e ignoramos los valores de f (n) y g (n) para valores pequeños de n.

f(n) = O(g(n)) significa literalmente "existe un valor n0 y una constante multiplicativa c tal que mientras n sea mayor que n0, f(n) será menor que c g(n).

Esta definición es relevante para el análisis de complejidad de algoritmos. Imagina que has escrito un algoritmo para ordenar una lista. Llamemos f (n) al número máximo de operaciones que su algoritmo necesita para ordenar una lista de elementos n. Quiere demostrar que su algoritmo es eficiente. Quieres hacer declaraciones como "f (n) = O (n ^ 2)", lo que significaría aproximadamente "si el tamaño de la lista se multiplica por 10, entonces el tiempo de ejecución se multiplicará por menos de 100" . Esto no da el número exacto de operaciones, tal vez f (n) = 4 n ^ 2, o tal vez f (n) = (n ^ 2 - n) / 2. Pero a quién le importa el número exacto. Lo importante es que si la lista es 10 veces más larga, el tiempo de ejecución será como máximo 100 veces más largo.

4
Stef 16 oct. 2020 a las 14:21