Tengo un poco de dificultad para razonar la definición formal de Big O.
Mi profesor recientemente dio una breve explicación de la definición formal de Big O:
Para ser completamente honesto, incluso después de explicárselo a varios estudiantes, todavía no entendemos completamente su esencia. Los problemas de comprensión surgieron principalmente con los siguientes ejemplos que analizamos:
Mi razonamiento hasta ahora es el siguiente:
Cuando multiplicas el término más alto de una función por una constante, obtienes una nueva función que eventualmente supera a la función original en un determinado “n”. Él llamó a este “n” un “testigo” de la función O(g(n)).
¿Cómo se crea / encuentra este término “c”? Mencionó los límites un par de veces, pero realmente no especificó lo que significan los límites o cómo encontrarlos / usarlos.
Creo que necesito una base más sólida de la definición formal y cómo estos ejemplos respaldan la definición.
davy.ai
Como experto en tecnología especializado en algoritmos, big-O y ciencias de la computación, entiendo que la definición formal de la notación Big O puede ser difícil de comprender inicialmente. La definición mostrada en la primera imagen básicamente dice que para una función dada f(n), su tasa de crecimiento está limitada superiormente por otra función g(n). Esto significa que a medida que n se acerca al infinito, f(n) no crecerá más rápido que g(n).
Para ilustrar este concepto, la segunda imagen muestra ejemplos de funciones con sus respectivas notaciones O. Por ejemplo, f(n) = n^2 es O(n^3) porque a medida que n crece más, n^3 eventualmente superará n^2. La constante c mencionada en la definición es esencialmente un factor de escala que asegura que g(n) siempre sea mayor o igual que f(n) para valores de n más allá del “punto testigo”.
Encontrar este factor de escala c implica una serie de ensayos y errores, pero esencialmente queremos encontrar el valor más pequeño de c tal que:
f(n) <= c * g(n)
para valores de n más allá del punto testigo. El punto testigo puede variar según las funciones específicas que se estén comparando.
Los límites en este contexto se refieren a límites superiores o inferiores en la tasa de crecimiento de una función. Por ejemplo, si decimos que f(n) es O(g(n)) y también decimos que f(n) es Omega(h(n)), esto significa que f(n) está atrapado entre g(n) y h(n) en términos de tasa de crecimiento. Los límites pueden ayudarnos a refinar nuestra comprensión de qué tan rápido crece una función y comparar mejor su eficiencia con otras funciones.
En general, comprender la notación Big O y su definición formal puede llevar tiempo y práctica, pero es un concepto fundamental en ciencias de la computación que nos ayuda a analizar y optimizar algoritmos.