Estás leyendo la publicación: ¿Qué es? – Hacia la IA
Publicado originalmente en Hacia la IA, la empresa líder mundial en noticias y medios de IA y tecnología. Si está creando un producto o servicio relacionado con la IA, lo invitamos a considerar convertirse en patrocinador de la IA. En Hacia la IA, ayudamos a escalar las empresas emergentes de IA y tecnología. Permítanos ayudarlo a dar rienda suelta a su tecnología a las masas.
Programación
Tenga en cuenta que al evaluar la complejidad del algoritmo, las constantes no se consideran porque no afectan significativamente el número de operaciones (cuando \ (n \) se vuelve muy grande). Por ejemplo, si el algoritmo se ejecuta en el orden n2, reemplace n con cn para indicar que el algoritmo se ejecuta en el orden c2n2 y la notación O grande ignora la constante c2. Por ejemplo, si el tiempo de ejecución de un algoritmo es O (n) cuando se mide por el número de dígitos n del número de entrada x, entonces cuando se mide en función del número de entrada, su tiempo de ejecución es O (log x). x porque n = O (log x).
O (1) significa que el algoritmo necesita un tiempo constante para ejecutarse independientemente del tamaño de la entrada. O (1) describe un algoritmo que siempre se ejecutará al mismo tiempo (o espacio) independientemente del tamaño del conjunto de datos de entrada. La notación Big-O puede expresar el tiempo de ejecución mejor, peor y promedio de un algoritmo. La notación Big-O es el lenguaje que usamos para hablar sobre el tiempo requerido para que se ejecute un algoritmo (complejidad de tiempo) o cuánta memoria usa el algoritmo (complejidad de espacio).
En computación, la notación O grande se usa para clasificar algoritmos en función de cómo crecen sus requisitos de espacio o tiempo de ejecución a medida que aumenta el tamaño de la entrada. La notación Big O es una notación matemática utilizada para clasificar algoritmos en función de cómo crecen sus requisitos de espacio o tiempo de ejecución a medida que aumenta el tamaño de la entrada. La notación Big O también se usa para denotar la complejidad del espacio, que funciona de la misma manera: cuánto espacio usa el algoritmo a medida que n aumenta la relación entre aumentar el tamaño de entrada y aumentar el espacio requerido.
Dado que la notación Big-O le indica la complejidad de un algoritmo en términos del tamaño de su entrada, es importante comprender Big-O si desea saber cómo se escalarán los algoritmos. El conocimiento de Big O es una herramienta esencial cuando se trabaja con algoritmos que deben operar a gran escala, lo que le permite tomar las decisiones correctas y reconocer las compensaciones cuando se trabaja con diferentes conjuntos de datos. Big-O Nation le ofrece una manera rápida y fácil de comunicar cómo se ejecuta un algoritmo. Una notación de O grande le permitirá medir diferentes algoritmos en función de la cantidad de pasos necesarios para completar y comparar el rendimiento de los algoritmos de manera objetiva.
El siguiente diagrama muestra las complejidades de Big-O mencionadas anteriormente y la cantidad de elementos en la entrada según la cantidad de operaciones. La complejidad está directamente relacionada con el tamaño de los datos de entrada: el algoritmo da un paso adicional para cada elemento de datos adicional. Estos algoritmos afectan en gran medida el rendimiento de cada elemento de entrada adicional.
Un algoritmo con complejidad de tiempo cuadrático tiene poca escalabilidad: si aumenta el tamaño de la entrada 10 veces, el tiempo aumenta 100 veces. De hecho, la complejidad temporal de Th (n log n) es muy cercana a la lineal: se tarda aproximadamente el doble de tiempo en resolver un problema del doble de tamaño. En cambio, podemos pensar en el tiempo como el número de operaciones o pasos necesarios para resolver un problema de dimensión n. En otras palabras, la notación Big-O es una forma de realizar un seguimiento de la rapidez con la que crece el tiempo de ejecución en relación con el tamaño de la entrada. Así, podemos decir que el tiempo de ejecución crece “en un orden del tamaño de la entrada” (O (n)) o en “el orden del cuadrado del tamaño de la entrada” (O (n2)).
Para el análisis sintáctico de O grande, nos preocupamos más de que las cosas crezcan más rápido a medida que crece la entrada porque todo lo demás se eclipsa rápidamente cuando n se vuelve muy grande. Para cualquier algoritmo, el análisis Big-O debería ser simple si definimos correctamente las operaciones que dependen de n, el tamaño de los datos de entrada. En general, lo hemos utilizado principalmente para medir y comparar las complejidades teóricas en tiempo de ejecución de los algoritmos para el análisis de rendimiento en el peor de los casos.
Esto a menudo se denomina “tiempo constante”. Si puede crear un algoritmo para resolver el problema en O (1), probablemente esté en camino. Algunos algoritmos, como el ordenamiento en cesta, tienen una complejidad espacial de O (n) pero pueden reducir la complejidad temporal a O (1). Por ejemplo, la ordenación por selección tiene una complejidad espacial de O (1) porque solo almacena el valor mínimo y su índice para comparar, el espacio máximo utilizado no aumenta con el tamaño de la entrada.
Por ejemplo, la complejidad temporal de una clasificación opcional puede determinarse mediante la función f (n) = n2/2-n/2, como se explicó en la sección anterior. Podemos simplificar la ecuación eliminando las constantes y todos los términos no dominantes. Cuando estás calculando la gran complejidad de algo, simplemente estás eliminando las constantes.
En términos generales, el valor constante de 1 es bastante insignificante al lado del valor de la variable n. Luego simplemente acortamos la expresión anterior a O (n) y ahí tenemos el tiempo de ejecución de Big-O print_values. A diferencia de O (N), que requiere un paso adicional para cada elemento de datos, O (log N) significa que el algoritmo da un paso adicional cada vez que se duplican los datos.
Esta instantánea rápida muestra cómo el rendimiento del primer algoritmo se relaciona con el valor de n. Cuanto mayor sea el número, más pasos tendrá que realizar el algoritmo. En general, cuando está interesado en la notación del algoritmo Big-O, está más interesado en el rendimiento general que en el análisis preciso de conteos de pasos. Para simplificar la notación, solo podemos indicar el valor de eficiencia.
Este registro le permitirá medir la tasa de crecimiento de su algoritmo en relación con los datos de entrada. Describe el peor de los casos para el rendimiento de su código. A continuación se muestra una hoja de trucos sobre la complejidad temporal y espacial de los algoritmos típicos.
A medida que estudie los algoritmos, aparecerán continuamente una serie de funciones de orden de magnitud muy comunes. Si estamos haciendo algo muy complejo, como con una función recursiva o un algoritmo de divide y vencerás, puedes usar el teorema principal (normalmente funciona) o, en casos ridículos, el teorema de Acra-Bazzi (casi siempre funciona) buscar la ejecución tiempo de su algoritmo en Wikipedia. Puede acelerar algunos algoritmos significativamente usando el almacenamiento en caché, haciendo que ignoren el caché, evitando cuellos de botella, trabajando desde la RAM en lugar del disco, usando la paralelización o trabajando antes de tiempo; estos métodos a menudo son independientes del orden de crecimiento. Notación Big O, aunque a menudo verá el número de núcleos en notación Big O para algoritmos paralelos. Como ingeniero de software, encontrará que la mayor parte de la discusión sobre Big-O se centra en el “límite superior” del tiempo de ejecución de un algoritmo, que a menudo se denomina el peor de los casos.
Big O describe específicamente el peor de los casos y se puede usar para describir el tiempo de ejecución requerido o el espacio utilizado (por ejemplo, Big O también se puede usar para describir el término de error al aproximar una función matemática. Notación Big-O (también llamada ” “crecimiento asintótico”) es cómo “se ven” las funciones cuando ignoras factores constantes y cosas cercanas al origen. La letra “n” aquí representa el tamaño de la entrada, y la función “g (n) = n2″ dentro ” O ()” nos da una idea de cuán complejo es el algoritmo dado el tamaño de los datos de entrada.
Notación Big O: ¿Qué es? se publicó originalmente en Hacia la IA en Medium, donde las personas continúan la conversación destacando y respondiendo a esta historia.
Publicado a través de Hacia la IA
