¿Cuál es exactamente la diferencia entre f (n) yg (n)?

Ambas son funciones de crecimiento (o a veces llamadas funciones de complejidad). Las funciones de crecimiento toman un número natural como entrada y producen un número real no negativo. Si uno dice [matemáticas] f (n) \ en O (g (n)) [/ matemáticas], lo que eso significa es que existe un positivo real [matemáticas] c [/ matemáticas] y un entero positivo [matemáticas] n_0 [/ matemática], de modo que para todos [matemática] n \ geq n_0 [/ matemática], [matemática] f (n) \ leq c \ cdot g (n) [/ matemática]. Big-Oh para una función de crecimiento dada es un conjunto de funciones de crecimiento. Por ejemplo [matemáticas] O (n) = \ {n, n + 1,2n, 4n + 2,8n,… \} [/ matemáticas]. Comúnmente usamos asintóticos al analizar un algoritmo porque:

• Normalmente tratamos problemas que tienen infinitas instancias de problemas. Queremos capturar el comportamiento de todas las instancias con un algoritmo, y algunas pueden ser tan grandes que no podrás comprenderlas. Los expresamos en términos del tamaño de entrada de un problema. Normalmente hablamos de algoritmos en términos de problemas, ya que un algoritmo toma como instancias de problemas de entrada y produce resultados para dicha instancia de problema.
• Queremos comparar algoritmos basados ​​en el orden de sus asintóticos. Normalmente usamos medidas de tiempo (pasos / ciclos / etc …) o espacio (memoria) en términos de asíntotics.

Para ayudarte aquí. Existen varios tipos de análisis que los teóricos usan al analizar un algoritmo. Hay el mejor análisis de casos, el análisis de casos promedio y el peor análisis de casos. Big-Oh es independiente de los tres, y es un error común pensar que Big-Oh siempre es para el análisis del peor de los casos. Esto no es verdad Al realizar su análisis, desea que sea lo más ajustado posible, por lo que generalmente desea Big-Theta. El análisis del peor de los casos significa que está seleccionando instancias que hacen que el algoritmo realice su peor desempeño, y luego cuenta esos pasos con respecto a la entrada (en palabras simples). Este tipo de análisis es útil porque sabe que el algoritmo no funcionará peor que esto. Es por eso que a menudo encontrarás teóricos que comparan sus algoritmos por su peor comportamiento, pero a veces el análisis de casos promedio es útil.

Por ejemplo, digamos que mi tarea es mostrar que [matemáticas] 4n \ en O (n ^ 2) [/ matemáticas] usando la definición de Big-Oh. Entonces, necesito encontrar una [matemática] c [/ matemática] y [matemática] n_0 [/ matemática] tal que para todos [matemática] n \ geq n_0 [/ matemática], [matemática] 4n \ leq c \ cdot n ^ 2 [/ matemáticas].

Elija [matemática] c = 1 [/ matemática] (hay varias que podría encontrar), luego necesitamos encontrar una [matemática] n_0 [/ matemática] tal que para todas [matemática] n \ geq n_0 [/ matemática] , [matemáticas] 4n \ leq n ^ 2 [/ matemáticas]. Bueno, [matemática] 4n \ leq n ^ 2 [/ matemática] si y solo si [matemática] 4 \ leq n [/ matemática], que se satisface cuando [matemática] n \ geq 4 [/ matemática]. Luego, elija [math] n_0 = 4 [/ math] (cualquier número mayor que cuatro funcionará, pero generalmente nos gusta cuando es muy ajustado). Por lo tanto, según la definición de Big-Oh, [matemáticas] 4n \ en O (n ^ 2) [/ matemáticas].

Algunas trampas comunes (que son muy comunes incluso con estudiantes universitarios en Ciencias de la Computación cuando he enseñado cursos que cubren esto en detalle):
-Los valores que encuentre para [math] c [/ math] y [math] n_0 [/ math] deben funcionar para todos los valores de [math] n \ geq n_0 [/ math], y debe demostrarlo para todos estos valores .
– Justifica lo que dices. Si simplemente arrojas un montón de desigualdades dando los significados de lo que estás diciendo, no tendrá mucho sentido. Uno no podrá distinguir si está afirmando su desigualdad o si demuestra que es válida.

¡Espero que esto ayude!

Son solo nombres de funciones. No hay nada mágico en el nombre “f” para una función; también puede preguntar cuál es la diferencia entre las variables a y b en álgebra. La respuesta, entonces, es que depende completamente del contexto.